백준16441 (아기돼지와 늑대) - 해결

아기돼지와 늑대

 

문제

산으로 둘러싸인 고리분지에 사는 아기돼지 삼형제는 엄마돼지로부터 독립하여 새 집을 지으려 합니다.

고리분지는 N × M 크기의 2차원 격자로 나타낼 수 있고 각 칸의 지형은 초원, 빙판, 산 중 하나입니다.

고리분지에는 돼지가족들 뿐만 아니라 늑대들도 살고 있습니다. 늑대는 상하좌우 인접한 칸 중 산이 아닌 칸으로 이동할 수 있습니다. 만약 이동한 칸이 빙판이라면 초원을 밟거나 산에 부딪칠 때까지 이동한 방향으로 미끄러집니다. 산에 부딪친 경우 늑대는 빙판 위에 가만히 서있을 수 있고 다시 다른 방향으로 이동할 수 있습니다.

게으른 아기돼지들은 지푸라기로 집을 지을 예정이기 때문에 늑대가 집이 있는 칸에 도착하기만 한다면 손쉽게 침입할 수 있습니다. 고리분지에 사는 늑대들이 도달할 수 없고 지형이 초원인 칸을 '안전한 곳'이라고 부릅니다. 게으른 아기돼지들을 위해 고리분지의 지도가 주어지면 지도 위에 모든 안전한 곳의 위치를 표시해주세요.

 

입력

첫 번째 줄에는 격자의 행의 수를 나타내는 N (3 ≤ N ≤ 100) 과 격자의 열의 수를 나타내는 M (3 ≤ M ≤ 100) 이 주어집니다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열들이 주어집니다. 

i+1번째 줄의 j번째 문자는 i번째 행 j번째 열의 지형 종류를 의미하며 '.' 일 경우 초원, '+' 일 경우 빙판, '#' 일 경우 산, 그리고 'W'는 늑대가 살고 있음을 나타냅니다. 늑대가 사는 칸은 여러 개일 수 있고 늑대가 사는 지형은 항상 초원입니다. 지도의 첫 번째, N번째 행과 첫 번째, M번째 열은 항상 산입니다.

 

출력

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

---

늑대 위치를 모두 저장하고 이를 하나씩 탐색하는 방법을 사용하였다.

일단 각 방향으로 탐색을 하였다.

초원이면 방문여부를 확인하고 q에 저장하고

늑대가 갈 수 있는 초원은 . => , 로 변경을 해주었다.

빙하면 같은 방향으로 빙하가 아닐 때 까지 이동해주었다.

산이라면 이전 장소가 방문했는지 확인을 하였다.

초원이라면 해당 장소가 방문했는지 확인을 하였다.

만약 늑대라면 거기서 출발한 적이 있기 때문에 제외하였다.

그리고 다 탐색을 하면 다시 , => . 로 . => P 로 변경하여 출력을 하였다.

 

핵심은 늑대가 방문할 수 있는 초원과 늑대가 방문할 수 없는 초원 구분.

그리고 빙하 끝에 도달하고 그곳이 산을 경우, 방문 여부 체크하는 방법. 이라고 생각한다.

첫 번째는 바로 생각을 하였지만 두번째는 바로 생각을 못해 여러번 시도를 하였다.

계속 시간 초과 발생 (해당 예시 사용)

input:
10 7
#######
#..+..#
###+###
#+W+++#
#+++#.#
##++++#
###.###
#+++++#
#.#+#.#
#######

output:
#######
#..+..#
###+###
#+W+++#
#+++#.#
##++++#
###.###
#+++++#
#P#+#P#
#######

import sys

input = sys.stdin.readline

N, M = map(int,input().split())

dirs = [(-1,0),(0,1),(1,0),(0,-1)]
# 맵
maps = []
# 늑대 위치
wolfs = []

for i in range(N):
    sub_map = list(input().strip())
    # 늑대 위치 저장
    for j in range(M):
        if sub_map[j] == 'W':
            wolfs.append((i,j))
    maps.append(sub_map)

visit = [[0] * M for _ in range(N)]

# 탐색
def dfs(wolf):
    q = [wolf]
    
    while q:
        now = q.pop()
        visit[now[0]][now[1]] = 1
        
        for dir in dirs:
            next_x = now[0] + dir[0]
            next_y = now[1] + dir[1]
            # 다음 장소가 범위안의 방문 안한 곳인지
            if 0 <= next_x < N and 0 <= next_y < M and visit[next_x][next_y] == 0:
                # 초원이 나오면 해당 장소를 저장하고 
                # 답 도출을 위해 다른 모양으로 바꿔주고
                # 방문으로 변경
                if maps[next_x][next_y] == '.':
                    q.append((next_x,next_y))
                    maps[next_x][next_y] = ','
                    visit[next_x][next_y] = 1
                # 빙판의 경우
                elif maps[next_x][next_y] == '+':
                    # 빙판이 아닌게 나올 때 까지 이동
                    while maps[next_x][next_y] == '+':
                        next_x += dir[0]
                        next_y += dir[1]
                    # 그 장소가 산이라면
                    if maps[next_x][next_y] == '#':
                        # 그 전 장소가 방문한 적이 있는지 확인
                        # 방문한 적이 없으면 저장
                        # 방문으로 변경
                        if visit[next_x - dir[0]][next_y - dir[1]] == 0:
                            q.append((next_x - dir[0],next_y - dir[1]))
                            visit[next_x- dir[0]][next_y- dir[1]] = 1
                    # 초원이고 방문을 안했다면
                    # 저장
                    elif maps[next_x][next_y] == '.' and visit[next_x][next_y] == 0:
                        q.append((next_x,next_y))
                        maps[next_x][next_y] = ','
                        visit[next_x][next_y] = 1
    

for wolf in wolfs:
    dfs(wolf)

# 늑대가 이동한 초원은 , => . 
# 늑대가 못 가는 초원은 . => P
for i in range(N):
    for j in range(M):
        if maps[i][j] == ',':
            maps[i][j] = '.'
        elif maps[i][j] == '.':
            maps[i][j] = 'P'

for m in maps:
    print(''.join(m))