[Python/백준] 3055 탈출

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

3055번: 탈출

<문제 해설>

BFS 문제이다. 고려해야할 점이 2가지가 있다.

1.  고슴도치도 이동하고 물도 이동하기때문에 이 둘을 같이 이동시킨다.
2. 고슴도치는 물이 차오르는 곳에 갈 수 없기 때문에 물을 먼저 이동시킨다. 이러면 물이 차오를 곳에 물이 들어가 있어서 고슴도치가 그곳으로 갈 수 없는 효과를 낸다.

이제 고슴도치가 방문했던 곳을 다시 방문하지 않고, 물이 있는 곳을 방문하지 않기 위해서 표시를 하면서 이동하면 된다.

고슴도치가 이동한 곳들은 배열로 저장해서 재귀함수로 넘겨주며 만약 재귀함수가 끝날때 고슴도치가 이동한 곳이 저장된 배열이 0이라면 더이상 이동할 곳이 없다는 뜻이기에 "KAKTUS"를 출력하면 된다.

<예시>

이 사진은 문제의 예제입력 3을 리스트로 나타냈다. 이제 고슴도치가 S로부터 출발하고 *에서 물이 출발한다. 고슴도치가 이동한 경로에는 0으로 표시가 남고 물이 이동하는 곳은 count가 표시된다.

함수를 다 돌릴 결과이다. 고슴도치가 D까지 6번 움직여서 도착한 걸 볼 수 있다.

이번 사진은 문제의 예제입력 2를 리스트로 나타냈다. 

이번에는 물이 찬곳을 고슴도치가 이동할 수 없기 때문에 2,0까지밖에 가지 못해서 "KAKTUS"를 출력한다.

<코드>

import sys

def bfs(S,water,count):
    nextS = []
    nextwater = []
    for w in water:
        for mv in move:
            x = w[1] + mv[1]
            y = w[0] + mv[0]
            if 0 <= x < C and 0 <= y < R:
                if jido[y][x] == '.':
                    jido[y][x] = count
                    nextwater.append([y,x])
    for s in S:
        for mv in move:
            x = s[1] + mv[1]
            y = s[0] + mv[0]
            if 0 <= x < C and 0 <= y < R:
                if [y,x] == D:
                    print(count)
                    return
                if jido[y][x] == '.':
                    jido[y][x] = 0
                    nextS.append([y,x])
    if len(nextS) == 0:
        print("KAKTUS")
    else:
        bfs(nextS,nextwater,count+1)
            
R, C = list(map(int,sys.stdin.readline().split()))

jido = []
water = []
move = [[0,1],[0,-1],[1,0],[-1,0]]
for i in range(R):
    line = list(sys.stdin.readline().rstrip())
    for j in range(C):
        if line[j] == 'D':
            D = [i,j]
        elif line[j] == 'S':
            S = [[i,j]]
        elif line[j] == '*':
            water.append([i,j])
    jido.append(line)

bfs(S,water,1)

<코드 설명>

import sys //sys를 사용하기 위한 라이브러리 import

def bfs(S,water,count): //bfs를 수행할 함수 호출 고슴도치가 간 곳들을 저장할 배열 S와 물이 차오르는 곳들을 표시할 water배열 그리고 몇분이 지났는지 표시할 count 함수가 있다.
    nextS = [] //다음 함수로 넘겨줄 S배열
    nextwater = [] //다음 함수로 넘겨줄 water배열
    for w in water: //water배열에서 갑을 받아서 w에 저장
        for mv in move: //움직임을 저장한 배열 x좌표 1증가, 1감소, y좌표 1증가, -1감소가 저장되어 있다(상하좌우 이동).
            x = w[1] + mv[1] //이동한 곳의 x좌표
            y = w[0] + mv[0] //이동한 곳의 y좌표
            if 0 <= x < C and 0 <= y < R: //이동한 곳이 지도의 좌표안에 있는지 확인하기
                if jido[y][x] == '.': // '.'일경우 여기로 이동할 수 있으니
                    jido[y][x] = count // 좌표의 지점을 count로 변경하고
                    nextwater.append([y,x]) //다음 함수로 넘겨준다
    for s in S: //water가 이동하는 방식과 같게 움직인다. 좌표는 nextS에 넣어준다.
        for mv in move:
            x = s[1] + mv[1]
            y = s[0] + mv[0]
            if 0 <= x < C and 0 <= y < R:
                if [y,x] == D:
                    print(count)
                    return
                if jido[y][x] == '.':
                    jido[y][x] = 0
                    nextS.append([y,x])
    if len(nextS) == 0: //만약 nextS가 비었다면 고슴도치가 더이상 갈곳이 없다는 의미여서 함수 재귀호출을 하지않는다.
        print("KAKTUS") //갈걸이 없으니 KAKTUS출력해준다
    else: //갈곳이있으면
        bfs(nextS,nextwater,count+1) //count를 증가시키고 재귀호출로 넘겨준다.
            
R, C = list(map(int,sys.stdin.readline().split())) //R,C를 정수형으로 받아오기

jido = [] //좌표값들을 받아올 배열
water = [] //물이 어디에 있는지 저장하는 변수
move = [[0,1],[0,-1],[1,0],[-1,0]] //이동하기위한 좌표들을 저장한 배열
for i in range(R): //R만큼 반복하면서
    line = list(sys.stdin.readline().rstrip()) //줄을 배열로 받아와서 line변수에 저장하기
    for j in range(C): //D,S,물이 있는지 확인하고 있다면 그들의 좌표를 저장해준다.
        if line[j] == 'D':
            D = [i,j]
        elif line[j] == 'S':
            S = [[i,j]]
        elif line[j] == '*':
            water.append([i,j])
    jido.append(line) //지도에 기록해주기

bfs(S,water,1) //함수에 값을 넣어준다.