[백준-파이썬] 16441: 아기돼지와 늑대

문제 보러 가기!
오랜만에 BFS를 풀어서 재미있었다~!

• 평범한 BFS 문제 + 빙판 부분이 특별했다.
• 먼저 늑대의 위치를 확인해서 리스트에 넣은 후에, 늑대 한 마리씩 확인했다. (늑대가 여럿 있을 수도 있음)
• 늑대가 방문할 수 있는 곳인지 방문 체크를 했다. (wolve_can_go 2차원 리스트)
• 빙판 부분은 while을 이용해서, 쭉~ 미끄러지듯 가줬다. 가고 있는 방향 쪽으로 한 칸 더 갔을 때(범위 확인 후)
  • 빙판이면 한 번 더 가기
  • 초원이라면 그만!(즉 늑대가 방문할 수 있다고 체크한 후, 큐에 넣었다.)
  • 산이라면 그 이전 위치에서 멈추도록 했다. (멈춰서 다른 방향 갈 수 있기 때문이다! 처음에 이 부분을 안 처리해서 틀렸다. 그 이전 위치를 방문 체크한 후, 큐에 그 이전 위치를 넣았다.)
• 범위 확인을 해줬는데, '지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산입니다.'라는 부분이 있으니까 산인지 확인해서 산이면 안 가게만 해줘도 될 것 같다.

코드 🧡

import sys, collections

input = sys.stdin.readline
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

N, M = map(int, input().split())
board = list(input().rstrip() for _ in range(N))
wolve_can_go = list([False] * M for _ in range(N))
ans = []

# 늑대 사는 곳
wolve = []
for i in range(N):
    for j in range(M):
        if board[i][j] == 'W':
            wolve.append((i, j))

# 늑대 사는 곳에서 출발!
for wolf in wolve:
    i, j = wolf
    q = collections.deque()
    q.append((i, j))
    wolve_can_go[i][j] = True  # 출발 지점 방문 체크
    while q:
        ii, jj = q.popleft()

        for k in range(4):
            ni, nj = ii + direction[k][0], jj + direction[k][1]
            if 0 <= ni < N and 0 <= nj < M and wolve_can_go[ni][nj] == False:  # 범위, 방문 체크
                if board[ni][nj] == '#':  # 산
                    wolve_can_go[ni][nj] = True
                    continue
                elif board[ni][nj] == '.':  # 초원 = 여기에 돼지 못 산다.
                    wolve_can_go[ni][nj] = True
                    q.append((ni, nj))
                elif board[ni][nj] == '+':  # 빙판 => 쭉 그 방향으로 미끌어 져야 함!
                    idx = 1
                    while True:
                        nni, nnj = ii + direction[k][0] * idx, jj + direction[k][1] * idx
                        if 0 <= nni < N and 0 <= nnj < M:
                            if board[nni][nnj] == '+':  # 이것도 빙판이면 더 가기
                                idx += 1
                            elif board[nni][nnj] == '.' and wolve_can_go[nni][nnj] == False:  # 초원이라면 그만
                                wolve_can_go[nni][nnj] = True
                                q.append((nni, nnj))
                                break
                            elif board[nni][nnj] == '#' and wolve_can_go[nni-direction[k][0]][nnj-direction[k][1]] == False:  # 산이라면 멈추기
                                wolve_can_go[nni-direction[k][0]][nnj-direction[k][1]] = True
                                q.append((nni-direction[k][0], nnj-direction[k][1]))
                                break
                            else:
                                break

                        else:  # 범위에 해당하지 않으면
                            break  # 그만!

for i in range(N):
    for j in range(M):
        if board[i][j] == '.' and not wolve_can_go[i][j]:
            print('P', end='')
        else:
            print(board[i][j], end='')
    print()