[백준 3055] 탈출

문제설명

https://www.acmicpc.net/problem/3055

3055번: 탈출

알고리즘

1. 그래프 정보 입력

2. 고슴도치 위치, 홍수 지역 정보 저장

3. 홍수 정보를 통해 1분당 홍수 그래프에 반영

4. 고슴도치 이동 반복

코드

import sys
from collections import deque
def Input_Data():
    R, C = map(int,readl().split())
    map_forest = [[0] + list(readl()[:-1]) + [0] if 1<=r<=R else [0]*(C+2) for r in range(R+2)]
    return R,C,map_forest
 
def Find_Dest():
    q = deque() #홍수 발생 지역 저장 
    x = y= dest_x = dest_y=0
    for i in range(1,R+1):
        for j in range(1,C+1):
            if map_forest[i][j] == 'S':   
                x,y =i, j
            if map_forest[i][j] == '*': #홍수 시작 지역 카운트 
                q.append((i,j))
    return x, y, q
 
def Raining(rain):
    next_rain = deque()
    while rain: 
        x, y = rain.popleft()
        for dx ,dy in d:
            nx,ny = dx+x, dy+y
            if not (1<=nx<=R and 1<=ny<=C): continue
            if map_forest[nx][ny] =='X' or map_forest[nx][ny] =='D' or map_forest[nx][ny] == '*': continue # 바위, 비버굴, 이미 홍수난 곳으로는 갈 수 없음      
            map_forest[nx][ny] = '*'
            next_rain.append((nx,ny))
    return next_rain
     
d= ((0,1),(0,-1),(1,0),(-1,0))
def Bfs(x_s,y_s, next_rain):   
    q = deque()
    new_q =deque()
    q.append((x_s, y_s,0))
    visited[x_s][y_s] = 1
    next_rain = Raining(next_rain) #홍수 진행
    while 1: 
        if len(new_q)>0 and len(q)==0:
            next_rain = Raining(next_rain) #홍수 진행
            q.extendleft(new_q)
            new_q =deque()
        elif len(new_q)==0 and len(q)==0:
            break
        x, y, cnt = q.popleft()
        for dx ,dy in d:
            nx,ny = dx+x, dy+y  
            if not (1<=nx<=R and 1<=ny<=C): continue
            if visited[nx][ny] !=0 : continue
            if map_forest[nx][ny] == '*' or map_forest[nx][ny] =='X': continue #홍수나 바위로는 갈 수 없음                 
            #이동할 수 있는 구역이면 
            if map_forest[nx][ny] == 'D':
                return visited[x][y] 
            if map_forest[nx][ny] == '.':
                new_q.append((nx,ny,cnt+1))
                visited[nx][ny] = visited[x][y] +1     
    return "KAKTUS"
 
readl = sys.stdin.readline

R, C, map_forest = Input_Data()
     
visited = [[0]*(C+2) for r in range(R+2)]
x_s, y_s, rain = Find_Dest()
sol=Bfs(x_s,y_s,rain)
 
 
print(sol)

고찰

이번 문제는 bfs탐색을 통해서 해결할 수 있는 문제였다

단, 물이 퍼지는 것과 캐릭터가 이동하는것을 동시에 고려해야하기 때문에 생각을 해야하는 문제였는데,

차근차근 짜서 순서에 맞게 구현하면된다

어려웠던 점은 queue를 각각 두개를 운용해서 써야한다 

반복해서 큐를 순회할때 새로나오는 건 새로운 큐에 저장하는 방식으로 구현할 수 있었다