[bfs/백준] 3055번 : 탈출

 - 문제 : https://www.acmicpc.net/problem/3055

 

Gold Lv4 문제이고, 풀이 없이 풀었다! 사실 이전에 풀었던 불 문제와 풀이가 비슷했다. 

 

문제 이해 

- 고슴도치(S)가 물이 번지는 상황에서 물에 잠기지 않고 무사히 비버 소굴(D)로 최소 시간에 갈 수 있는지 확인하는 문제다.

- 고슴도치와 물 둘 다 bfs로 진행해야하기 때문에 둘다 모두 queue에 넣어서 진행해야한다.

- 고슴도치는 matrix에서 '.', 'D'인 지점을 지날 수 있고, 물은 '.' 인 지점만 갈 수 있다.

하지만 시간을 아끼기 위해서는 고슴도치와 물 모두 각 지점이 ' . '이거나 'D'인 지점을 탐색할 수 있게 했다. (물은 'D' 지점을 못 가기 때문에 추가 조건을 달아준다, 이렇게 한 이유는 이전에 고슴도치, 물 각각 따로 분기문으로 나눠서 진행했는데 시간초과가 발생했기 때문이다)

- 고슴도치가 가는 길은 양의 정수로 진행하고, 물이 지나가는 곳은 -1 처리를 해서 고슴도치가 못가게 한다.

 

 

풀이 로직

- 입력값(n, m, matrix)을 입력받으면서 고슴도치의 위치, 비버 소굴의 위치, 물의 위치를 저장한다. 

- queue에 이동하는 위치를 추가할 건데, 이때 어떤 객체가 움직이는지 확인하기 위해 [행, 열, 'kaktus'(고슴도치)'], [행, 열, 'water'(물)]의 형태로 데이터를 추가한다. 

- 물의 위치는 queue에 입력하고, 고슴도치와 비버 소굴의 위치는 (a, b), (c, d)에 입력한다.

     - 고슴도치와 물의 초기 위치를 visit에 기록한다. (고슴도치는 visit[i][j] = 1, 물은 visit[i][j] = -1 -> 이렇게 초기 설정을 하지 않으면            틀리거나 시간초과가 발생한다)

     - 물(*)의 위치를 queue에 먼저 넣는 이유는 고슴도치는 물이 번질 곳으로는 이동하면 안되기 때문이다.

- while문을 진행하면서 도착한 위치가 비버 소굴이고, 객체가 고슴도치라면 정답이므로 답을 저장한 다음, flag = True 설정 후 break한다.

    - 답이 visit[x][y] - 1인 이유는 처음 시작을 1로 시작했기 때문에 정답보다 1 크기 때문이다.

- 아직 도착하지 않았다면 범위 내에서 상하좌우를 탐색한다. 이때 각 노드들은 다음 노드를 방문하지 않았고, matrix의 값이 '.' 또는 'D'인 지점만 방문 가능하다. 

- 고슴도치인 경우 visit[다음노드]로 시간 1을 들여 이동한다. 물이라면 matrix == '.' 인 지점만 이동 가능하고, visit[다음노드]를 -1 처리하고 이동한다. 

- 만약 반복문을 다 돌아도 flag == False 라면 실패한 것이므로 'KAKTUS'를 출력한다. 아니라면 그대로 정답을 출력하면 된다.

 

 

정답풀이 

n, m = map(int, input().split())
matrix = []
a, b = 0, 0 # 고슴도치 위치 
c, d = 0, 0 # 비버 소굴 위치
queue = []
visit = [[0] * m for _ in range(n)]
for i in range(n):
    matrix.append(list(input()))
    for j in range(m):
        if matrix[i][j] == 'D':
            c, d = i, j
        if matrix[i][j] == 'S':
            a, b = i, j
            visit[i][j] = 1
        if matrix[i][j] == '*':
            queue.append([i, j, 'water'])
            visit[i][j] = -1
            
queue.append([a, b, 'kaktus'])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
answer = 0
flag = False
while queue:
    x, y, kind = queue.pop(0)
    
    if x == c and y == d:
        if kind == 'kaktus':
            flag = True
            answer = visit[x][y] - 1
            break
    
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if not visit[nx][ny] and (matrix[nx][ny] == '.' or matrix[nx][ny] == 'D'):
                if kind == 'kaktus':
                    visit[nx][ny] = visit[x][y] + 1
                    queue.append([nx, ny, 'kaktus'])
                if kind == 'water':
                    if matrix[nx][ny] == '.':
                        visit[nx][ny] = -1
                        queue.append([nx, ny, 'water'])
                    
if flag == False :
    print('KAKTUS')
else:
    print(answer)