[파이썬] 백준 16441 : 아기돼지와 늑대 (골드3)

[파이썬] 백준 16441 : 아기돼지와 늑대 (골드3)

16441번: 아기돼지와 늑대

---

문제

 

---

풀이

0. 방향성 생각

• 빙판이 들어가는 방향마다 이동경로가 다르게 처리된다. 같은 빙판에 접근하더라도 들어가는 방향에 따라 다를 수 있기 때문에, 좌표에 대해서 방문처리하면 다른 방향으로 못갈 수도 있다.
• visit 좌표 위치에 4방향을 넣어서 방문체크를 한다.

1. 입력

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
visit = [[[False]*4 for _ in range(w)] for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

q = deque()
for i in range(h):
    for j in range(w):
        if arr[i][j] == 'W':
            visit[i][j] = [True]*4
            q.append((j,i))

• 늑대가 시작점은 모두 방문처리 해주고 큐에 추가.

2. 함수 정의

while q:
    x,y = q.popleft()

    for d in range(4):
        dx,dy = dire[d]
        nx,ny = x+dx,y+dy
        nxt = arr[ny][nx]

        if not visit[ny][nx][d]:         
            if nxt == '.' or nxt == 'W':
                visit[ny][nx][d] = True
                q.append((nx,ny))
            elif nxt == '+':          

                for i in range(100):
                    nnx,nny = nx+i*dx,ny+i*dy
                    nnxt = arr[nny][nnx]
                    if not visit[nny][nnx][d]:
                        if nnxt == '.' or nnxt == 'W':
                            visit[nny][nnx][d] = True
                            q.append((nnx,nny))
                            break
                        elif nnxt == '#':
                            q.append((nnx-dx,nny-dy))
                            break
                        else:
                            visit[nny][nnx][d] = True
                    else:
                        break

• 다음 위치가 초원이면 해당 초원으로 들어가는 방향으로 방문처리 해주고 해당 좌표를 큐에 추가.
• 빙판을 밟은 경우 앞으로 계속 전진하는 코드를 for문으로 구현했다.
• 해당 빙판 방향으로 접근한 적이 없는 경우, 그 방향으로 visit을 계속 True를 해준다.
• 산을 만난 경우 nnx-dx,nny-dy로 산 이전의 좌표를 큐에 넣어준다. 더 전진하지 못하므로 break
• 초원을 만난 경우 바로 멈출 수 있으니, 방문처리하고 큐에 넣고 탈출
• 만약 해당 방향 빙판으로 접근했으면 for문 돌릴 필요 없으니 바로 탈출

3. 출력

for i in range(h):
    s = ''
    for j in range(w):
        if arr[i][j] == '.':
            s += '.' if any(visit[i][j]) else 'P'
        else:
            s += arr[i][j]
    print(s)

• visit의 해당 좌표에서 하나라도 True 체크가 되어있으면 안전하지 않으므로 .
• 모두 False이면 P
• 그렇지 않은 경우 그대로 복사해주기.

 

---

전체코드

from collections import deque
import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
arr = [list(input()) for _ in range(h)]
visit = [[[False]*4 for _ in range(w)] for _ in range(h)]
dire = [(1,0),(0,1),(-1,0),(0,-1)]

q = deque()
for i in range(h):
    for j in range(w):
        if arr[i][j] == 'W':
            visit[i][j] = [True]*4
            q.append((j,i))
while q:
    x,y = q.popleft()

    for d in range(4):
        dx,dy = dire[d]
        nx,ny = x+dx,y+dy
        nxt = arr[ny][nx]

        if not visit[ny][nx][d]:         
            if nxt == '.' or nxt == 'W':
                visit[ny][nx][d] = True
                q.append((nx,ny))
            elif nxt == '+':          

                for i in range(100):
                    nnx,nny = nx+i*dx,ny+i*dy
                    nnxt = arr[nny][nnx]
                    if not visit[nny][nnx][d]:
                        if nnxt == '.' or nnxt == 'W':
                            visit[nny][nnx][d] = True
                            q.append((nnx,nny))
                            break
                        elif nnxt == '#':
                            q.append((nnx-dx,nny-dy))
                            break
                        else:
                            visit[nny][nnx][d] = True
                    else:
                        break

for i in range(h):
    s = ''
    for j in range(w):
        if arr[i][j] == '.':
            s += '.' if any(visit[i][j]) else 'P'
        else:
            s += arr[i][j]
    print(s)

 

코멘트

다 풀어놓고 복붙하다가 로직 변경하는거 조금씩 빼먹는데 주석 달아서 체크하면서 넘어가기