[파이썬] 백준 17267: 상남자 (플레5)

[파이썬] 백준 17267: 상남자 (플레5)

• https://www.acmicpc.net/problem/17267

 

 

---

풀이

방향성 생각

• 유니온 파인드로 세로단위 + 벽으로 나뉜 구분으로 나눠서 유니온 파인드로 풀려고 했다
• 단위가 세로랑 벽으로 나뉘면 애초에 같은 노드라고 구분지을 수 있어서 0-1너비우선처럼 풀이
• 세로로 이동하면 덱 맨 앞으로, 가로로 이동하면 덱 맨 뒤로 넣기.

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()
inside = lambda x,y : 0<=x<W and 0<=y<H
dire = [(1,0),(0,1),(-1,0),(0,-1)]

H,W = map(int,input().split())
left,right = map(int,input().split())

arr_raw = [list(input()) for _ in range(H)]
arr = []

# int로 변환
for i in range(H):
    arr.append(list(map(int,arr_raw[i])))
    for j in range(W):
        if arr_raw[i][j] == '2':
            sx,sy = j,i

# x,y,남은 left이동, 남은right이동
Q = deque([(sx,sy,left,right)])
V = [[False]*W for _ in range(H)]
V[sy][sx] = True
while Q:
    x,y,l,r = Q.popleft()
    for idx,(dx,dy) in enumerate(dire):
        nx,ny = x+dx,y+dy
        is_ver = idx%2
        if inside(nx,ny) and not V[ny][nx] and arr[ny][nx] != 1:
            if is_ver:
                V[ny][nx] = True
                Q.appendleft((nx,ny,l,r))
            else:
                if idx==0 and r:
                    V[ny][nx] = True    
                    Q.append((nx,ny,l,r-1))
                elif idx==2 and l:
                    V[ny][nx] = True    
                    Q.append((nx,ny,l-1,r))

answer = sum(sum(V[i]) for i in range(H))
print(answer)

---

코멘트

• .