[백준] 3055 탈출 [Python]

 

위의 문제는 bfs를 활용해서 고슴도치가 비버의 집을 찾아가는 시간을 출력하는 문제입니다.

 

이 문제를 풀 때 고슴도치를 먼저 이동할지 물을 이동할지 고민을 하다가 저는 고슴도치를 먼저 이동하고 물을 이동하는 방식으로 풀어봤습니다. 

 

이렇게 하면 물이 다음에 이동할 거리를 생각안해도되므로 고슴도치의 조건이 하나 줄어듭니다.

 

    R,C = map(int,s.readline().split())
    graph = [list(map(str,s.readline().strip())) for _ in range(R)]
    
    v = [[0]*C for _ in range(R)]
    q = deque()

 

우선 진행에 필요한 데이터들을 미리 생성해두고 bfs함수와 조건들을 생성합니다.

 

    #비버 집 위치 저장
    for i in range(R):
        for j in range(C):
            if graph[i][j]=='D':
                c,d = i,j
                
    #고슴도치 위치 찾고 q에 저장 
    for i in range(R):
        for j in range(C):
            if graph[i][j]=='S':
                x,y =i,j
                q.append((x,y))
                     
    #물의 위치 찾고 q에 저장
    for i in range(R):
        for j in range(C):
            if graph[i][j]=='*':
                q.append((i,j))
    
    bfs(x,y)

 

우선 bfs에 들어가기전에 비버의 집위치를 찾아서 저장해둡니다.

 

그리고 고슴도치와 물의 위치를 찾는데 저는 고슴도치 이동 후 물을 이동시킬 꺼니까 차례대로 q에 넣어서 bfs함수를 호출합니다.

 

def bfs(si,sj):
    v[si][sj]=1
    
    while q:
        ci,cj = q.popleft()
        
        #네 방향 확인에 필요한 dx,dy
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
                
        for i in range(4):
            nx = ci + dx[i]
            ny = cj + dy[i]
            
            #현재 graph값이 S이고 다음 graph값이 . 또는 D 일떄 방문
            if 0<=nx<R and 0<=ny<C and (graph[nx][ny]=='.' or graph[nx][ny]=='D') and graph[ci][cj]=='S':
                v[nx][ny] = v[ci][cj]+1
                graph[nx][ny]='S'
                q.append((nx,ny))
            
            #현재 graph값이 *이고 다음 graph값이 . 또는 S 일때 방문
            elif 0<=nx<R and 0<=ny<C and (graph[nx][ny]=='.' or graph[nx][ny]=='S') and graph[ci][cj]=='*':
                graph[nx][ny]='*'
                q.append((nx,ny))

 

q에서 차례대로 빼고 고슴도치먼저 네 방향을 탐색 후 방문처리합니다. 방문처리 할때에는 이동할 때 시간을 기록해야 하므로 현재 값에 +1을 해줘서 마지막에 비버의집에 도착했을 때 그 값을 찾습니다.

 

이 코드에서 주의해야 할 점은 if, elif의 조건입니다.

 

현재 graph[ci][cj]값이 S일때와 *일때만 이동하게해서 고슴도치가 물에 잠겼을 때에는 q에는 존재하지만 현재 값이 다르므로 비버의 집까지 도달하지 못합니다.

 

이렇게 bfs가 끝나게되면 비버의 집에 도달하면 그 값을 구해서 출력하고 만약 도달하지 못하면 KAKTUS를 출력하면됩니다.

 

전체 코드

from sys import stdin as s
from collections import deque

s = open('input.txt','rt')

#S의 좌표를 받아와서 시작
def bfs(si,sj):
    v[si][sj]=1
    
    while q:
        ci,cj = q.popleft()
        
        #네 방향 확인에 필요한 dx,dy
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
                
        for i in range(4):
            nx = ci + dx[i]
            ny = cj + dy[i]
            
            #현재 graph값이 S이고 다음 graph값이 . 또는 D 일떄 방문
            if 0<=nx<R and 0<=ny<C and (graph[nx][ny]=='.' or graph[nx][ny]=='D') and graph[ci][cj]=='S':
                v[nx][ny] = v[ci][cj]+1
                graph[nx][ny]='S'
                q.append((nx,ny))
            
            #현재 graph값이 *이고 다음 graph값이 . 또는 S 일때 방문
            elif 0<=nx<R and 0<=ny<C and (graph[nx][ny]=='.' or graph[nx][ny]=='S') and graph[ci][cj]=='*':
                graph[nx][ny]='*'
                q.append((nx,ny))     
              

if __name__=='__main__':
    R,C = map(int,s.readline().split())
    graph = [list(map(str,s.readline().strip())) for _ in range(R)]
    
    v = [[0]*C for _ in range(R)]
    q = deque()
    
    #비버 집 위치 저장
    for i in range(R):
        for j in range(C):
            if graph[i][j]=='D':
                c,d = i,j
                
    #고슴도치 위치 찾고 q에 저장 
    for i in range(R):
        for j in range(C):
            if graph[i][j]=='S':
                x,y =i,j
                q.append((x,y))
                     
    #물의 위치 찾고 q에 저장
    for i in range(R):
        for j in range(C):
            if graph[i][j]=='*':
                q.append((i,j))
    
    bfs(x,y)
    
    #bfs종료후에 v배열확인 후 원하는 값 출력
    if v[c][d]:
        print(v[c][d]-1)
    else:
        print('KAKTUS')