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

백준 16441 - 아기돼지와 늑대

시간 제한 1초, 메모리 제한 256MB

# 조건

• 산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다.
• 고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다.
• 고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다.
• 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다.
  • 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다.
  • 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다.
• 게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다.
• 고리분지에 사는 늑대들이 도달할 수 없고 지형이 초원인 칸을 '안전한 곳'이라고 부릅니다.
• 게으른 아기돼지들을 위해 고리분지의 지도가 주어지면 지도 위에 모든 안전한 곳의 위치를 표시해주세요.

입력

• 첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다.
• 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열들이 주어집니다.
• i+1번째 줄의 j번째 문자는 i번째 행 j번째 열의 지형 종류를 의미하며 '.' 일 경우 초원, '+' 일 경우 빙판, '#' 일 경우 산, 그리고 'W'는 늑대가 살고 있음을 나타냅니다.
• 늑대가 사는 칸은 여러 개일 수 있고 늑대가 사는 지형은 항상 초원입니다.
• 지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산입니다.

출력

• 입력으로 주어진 지도를 출력하되 아기돼지가 살 수 있는 초원은 문자 'P'로 대체하여 출력합니다.

# 접근 방법

• 입력을 받은 후 늑대 위치와 초원 위치를 리스트와, 딕셔너리에 기록해준다.
• 늑대의 경우 - 번호 : 인덱스, 초원의 경우 (x좌표, y좌표) : 1
• 늑대를 순회하며 위의 조건에 따라 이동시켜준다.
  • 초원을 밟는 경우 초원 딕셔너리에서 0으로 변경해준다.
  • 빙판을 밟는 순간 이동 가능한 방향으로 이동하며 초원인 경우 초원을 q에 넣어주고, 산을 만나는 경우 마지막 빙판을 q에 넣어준다.
• 늑대가 이동가능한 모든 곳을 확인 한 후 초원 딕셔너리에 남아있는 곳을 P로 변경한 후 출력해주면 된다.
• 주의할 점은, visited 처리를 모두 해주지만, 빙판을 만나서 초원 또는 산을 만나러 갈 때에는 visited를 확인해주지 않아야 한다.
• 아래와 같은 경우 아래에서 위로 올라오는 빙판길이 존재하지만 중간에 빙판길이 먼저 VISITED 처리가 되어 1행의 초원을 밟지 못하는 경우가 발생할 수 있기 때문이다.

  # # . # #
  W + + + #
  . # + # #
  . # + # #
  . . . # #

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from collections import deque  

def bfs():  
    visited = [[0] * M for _ in range(N)]  
    # 모든 늑대들 q에 넣어주기 + 이동방향 -1로  
    q = deque()  
    for i, j in wolf:  
        q.append((i, j))  
        visited[i][j] = 1  
    while q:  
        si, sj = q.popleft()  
        for d in range(4):  
            ni, nj = si+ di[d], sj + dj[d]  
            if 0<=ni<N and 0<=nj<M:  
                # 초원이라면 바로 q에 추가  
                if arr[ni][nj] == '.' and visited[ni][nj] == 0:  
                    q.append((ni, nj))  
                    grassland[(ni, nj)] = 0  
                    visited[ni][nj] = 1  
                # 빙판이라면 끝까지 가기  
                elif arr[ni][nj] == '+':  

                    while 0<=ni<N and 0<=nj<M:  
                        # 산이라면 하나빼서 저장  
                        if arr[ni][nj] == '#':  
                            ni -= di[d]  
                            nj -= dj[d]  
                            break  
                        elif arr[ni][nj] == '.':  
                            # 초원인 경우 방문하지 않았다면 표시  
                            if visited[ni][nj] == 0:  
                                grassland[(ni, nj)] = 0  
                            break  
                        ni += di[d]  
                        nj += dj[d]  

                    # 첫방문이면 방문처리  
                    if visited[ni][nj] == 0:  
                        visited[ni][nj] = 1  
                        q.append((ni, nj))  




N, M = map(int, input().split())  
arr = [list(input().rstrip()) for _ in range(N)]  
di, dj = [1, -1, 0, 0], [0, 0, 1, -1]  

wolf = []  
grassland = dict()  
for i in range(N):  
    for j in range(M):  
        # 늑대 위치 기록  
        if arr[i][j] == 'W':  
            wolf.append((i, j))  

        elif arr[i][j] == '.':  
            grassland[(i, j)] = 1  

bfs()  

for loc, can in grassland.items():  
    if can:  
        arr[loc[0]][loc[1]] = 'P'  

for i in arr:  
    print(''.join(i))