[백준] 3055 탈출 - python 파이썬

문제

 

 

 

이 문제는 어떤 알고리즘을 사용해야할 지는 쉽게 감이 잡히는데 조건이 많아서 이걸 다 충족하면서 구현하는게 까다로웠던 문제이다.

특히 BFS를 활용하는데 이동대상이 하나가 아니다보니 이걸 변형하는걸 생각하는게 어려웠던 문제였던 것 같다. (사실 조금만 변형하면 되는 문제임에도 불구하고 처음으로 접해보다보니 고정관념에 사로잡혀 쉽게 생각해주지 못햇던 것 같다.)

 

 

일단 BFS 알고리즘을 활용하는데 이때 while문을 돌때 보통 하나의 대상에 대해서만 이동가능 좌표를 추가해줬다면

 

이 문제에서는 고슴도치의 이동 가능 좌표, 물의 이동가능 좌표를 같이 추가해주면 된다.

 

정답코드

from collections import deque

r,c = map(int, input().split())
graph = [list(input().strip()) for _ in range(r)]
visited = [[0]*c for _ in range(r)]



dx = [1,-1,0,0]
dy = [0,0,-1,1]

def bfs(si,sj):

    #0부터 시작한게 아니므로 나중에 1 빼주어야함 
    visited[si][sj] = 1

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<= nx <r and 0<= ny <c:
                #물이 확산하는 부분 처리
                if (graph[nx][ny] =='.' or graph[nx][ny] == "S") and graph[x][y] == '*':
                        graph[nx][ny] = '*'
                        q.append((nx,ny))
                #비버가 이동하는 부분 처리
                elif (graph[nx][ny] =='.' or graph[nx][ny] == "D") and graph[x][y] == 'S':
                        visited[nx][ny] = visited[x][y] +1
                        graph[nx][ny] = 'S'
                        q.append((nx,ny))

                


q = deque()

for i in range(r):
    for j in range(c):
        #고슴도치위치저장
        if graph[i][j] == 'S':
            si,sj = i,j
            q.append((si,sj))

for i in range(r):
    for j in range(c):
        #비버의 굴 위치 저장
        if graph[i][j] == "D":
            di = i
            dj = j

for i in range(r):
    for j in range(c):
        #물의 위치 저장
        if graph[i][j] == "*":
            wi = i
            wj = j
            #이때 물의 위치가 여러개일 수 있으므로 꼭 for문 안에서 찾을 때마다 q에 추가해주어야함
            q.append((wi,wj))




bfs(si,sj)

if visited[di][dj]:
    #처음 시작점이 0이 아니라 1부터 시작했으므로 1빼줌
    print(visited[di][dj] - 1)
else:
    #비버의 굴이있는 곳에 도달한 적이 없는 것이므로 예외처리
    print("KAKTUS")

 

 

 

 

 

사실 구글링을 해서 정답을 알게된건데 정답 코드를 보면서도  물이 확산되는걸 처리하는 것과 고슴도치가 이동하는 것을 처리하는 부분이 왜 같은 큐에 들어가도 되는지를 잘 이해하지 못했었다.

 

 

그치만 BFS의 작동 원리를 잘 생각 해보면 금방 이해할 수 있다.

BFS는 "레벨 단위" 로 동작되기 때문에 현재 레벨에서의 고슴도치와 물을  같이 처리한 후 다음 레벨로 넘어가기 때문에 같은 큐에 넣어주어도 되는 것이다. 

 

그리고 물이 확산되는 것이 고슴도치의 이동가능경로 계산에 영향을 미치지 때문에 같은 큐에 한번에 넣어주어야한다.