백준 3055 탈출 Python 3

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

3055번: 탈출

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ3055.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
from collections import deque

def fill_up_water():
    edge = len(water)
    while edge:
        x, y = water.popleft()
        for ddx, ddy in zip(dx, dy):
            nx, ny = x+ddx, y+ddy
            if 0 <= nx < C and 0 <= ny < R and forest[ny][nx] == '.':
                forest[ny][nx] = '*'
                water.append([nx, ny])
        edge -= 1

def escape():
    while q:
        fill_up_water()

        edge = len(q)
        while edge:
            x, y, mins = q.popleft()
            if forest[y][x] == 'D':
                print(mins)
                return
            for ddx, ddy in zip(dx, dy):
                nx, ny = x + ddx, y + ddy
                if 0 <= nx < C and 0 <= ny < R:
                    if (forest[ny][nx] == '.' or forest[ny][nx] == 'D') and not visit[ny][nx]:
                        visit[ny][nx] = 1
                        q.append([nx, ny, mins+1])
            edge -= 1
    print("KAKTUS")
    return

input = sys.stdin.readline
R, C = map(int, input().split())
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
forest = []
q = deque(list())
water = deque(list())
visit = [[0]*C for _ in range(R)]
for r in range(R):
    forest.append(list(input().rstrip()))
    for c in range(C):
        if forest[r][c] == 'S':
            q.append([c, r, 0])
            visit[r][c] = 1
            forest[r][c] = '.'
        elif forest[r][c] == '*':
            water.append([c, r])
escape()

---

풀이 과정

풀이 시간 38분

백준 5427 불 문제랑 아주 유사한 문제다.

2022.02.07 - [코테 노트/백준] - 백준 5427 불 Python 3

백준 5427 불 Python 3

 

S에서 D로 가기 위해 한 칸씩 이동하는데 물이 있는 곳이나 곧 차오를 예정인 칸으로 이동은 불가하다는 것이 핵심이다.

즉, 매 분마다 물이 인접한 칸으로 차오르는 로직을 먼저 수행한 후에 고슴도치를 빈 곳으로 한 칸 이동시키면 된다.

이를 위해 물이 인접한 칸으로 번지는 BFS와 고슴도치를 이동시키는 BFS가 필요하다.

import sys
from collections import deque

def fill_up_water():
	#현 1분 동안 퍼뜨려야하는 물만 퍼뜨리기 위해 edge만큼 while문 반복
    edge = len(water)
    
    while edge:
        x, y = water.popleft()
        
        #인접한 4방향 탐색
        for ddx, ddy in zip(dx, dy):
            nx, ny = x+ddx, y+ddy
            #범위 안에 있으면서 빈 곳이라면 물을 퍼뜨린다
            if 0 <= nx < C and 0 <= ny < R and forest[ny][nx] == '.':
                forest[ny][nx] = '*'
                water.append([nx, ny])
        edge -= 1

def escape():
    while q:
    	#물을 퍼뜨린다
        fill_up_water()
		
        #현재 시간에 고슴도치의 가능한 위치들만 한 칸 이동시켜야 하므로 edge만큼만 while문 반복
        edge = len(q)
        while edge:
            x, y, mins = q.popleft()
            
            #비버의 굴에 도착한 경우, 함수 종료
            if forest[y][x] == 'D':
                print(mins)
                return
            
            #인접한 4방향 탐색
            for ddx, ddy in zip(dx, dy):
                nx, ny = x + ddx, y + ddy
                if 0 <= nx < C and 0 <= ny < R:
                	#비버의 굴이거나 빈 곳이면서 이전에 방문하지 않은 곳인 경우, 방문처리 후 큐에 담는다
                    if (forest[ny][nx] == '.' or forest[ny][nx] == 'D') and not visit[ny][nx]:
                        visit[ny][nx] = 1
                        q.append([nx, ny, mins+1])
            edge -= 1
    
    #while문이 정상 종료된 경우, 모든 칸을 탐색했지만 비버의 굴에 도착하지 못한 경우이므로 탈출 실패
    print("KAKTUS")
    return

input = sys.stdin.readline
R, C = map(int, input().split())

#좌, 상, 우, 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

forest = []
#고슴도치의 위치와 이동한 시간을 담는 큐
q = deque(list())
#퍼뜨릴 물의 시발점을 담은 큐
water = deque(list())
visit = [[0]*C for _ in range(R)]

for r in range(R):
    forest.append(list(input().rstrip()))
    for c in range(C):
    	#고슴도치의 시작 위치와 0분을 q에 담고 방문처리 한다
        if forest[r][c] == 'S':
            q.append([c, r, 0])
            visit[r][c] = 1
            forest[r][c] = '.'
            
        #초기 물이 있는 위치를 water에 담는다
        elif forest[r][c] == '*':
            water.append([c, r])
escape()

#시간복잡도 = O(V+E), 공간복잡도 = O(n)