3055

날짜 : 2023. 04. 29

사용 언어 : python

 

문제

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

 

 

코드

import sys
from collections import deque
r, c = map(int, sys.stdin.readline().split())
graph = list()
for _ in range(r):
    graph.append(' '.join(sys.stdin.readline().rstrip()).split())
#print(graph)
dest = 0


def bfs(a, b, check):  # 행, 열, 상태
    graph[a][b] = 0
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    queue = deque()
    queue.append([a, b, 0])
    while queue:
        p, q, cnt = queue.popleft()
        for i in range(4):
            x = p + dx[i]
            y = q + dy[i]
            if x in range(r) and y in range(c):
                if graph[x][y] == ".":
                    graph[x][y] = cnt + 1  # 방문시점 기록
                    queue.append([x, y, cnt + 1])
                elif graph[x][y] == "D" and check == "S":
                    global dest
                    dest = cnt+1
                    return True
                elif graph[x][y] == "D" or graph[x][y] == "X": continue
                elif graph[x][y] in range(200):  # 숫자인 경우(물이 차오를 예정)
                    if graph[x][y] > (cnt + 1):  # 선방문 가능
                        graph[x][y] = cnt + 1
                        queue.append([x, y, cnt + 1])
    return False

for i in range(r):
    for j in range(c):
        if graph[i][j] == "*":
            bfs(i, j, graph[i][j])  # 물부터 확인
"""for i in graph:
    print(i)"""
for i in range(r):
    for j in range(c):
        if graph[i][j] == "S":
            if bfs(i, j, graph[i][j]):
                print(dest)
            else:
                print("KAKTUS")
"""for i in graph:
    print(i)"""

 

 

풀이

- 고슴도차(S)가 이동할 때 물이 이미 차오른 경우 이동할 수 없는 케이스가 있기 때문에 물이 차오르는 시간을 미리 그래프에 적용한 후에 고슴도치를 이동시킨다.

- 즉, bfs를 각각 물("*"), 고슴도치("S")를 기준으로 해서 두 번 돌리는 케이스가 된다.

- 그 다음 조건에 맞게 빈 공간(".")일 때에는 물이 차오르는 시점으로 교체하고, 돌이나 비버의 집("D")을 만나는 경우에는 물이 차오를 수 없기 때문에 skip한다.

-  그 다음 고슴도치에 대하여 bfs()를 돌리는 경우 물이 차오르는 경우와 동일하되, 해당 위치의 값이 정수일 때 값이 더 작다면 이를 갱신한다.(물이 차오르기 전에 해당 위치에 도달 가능)

- 이후 "D"에 도달했을 때에는 자연스럽게 값을 도출할 수 있기 때문에 최종값(dest)를 최신화하고, True를 리턴한다.

- 해당 bfs에서 False가 리턴되면 물이 차올라 "D"에 도달하지 못한 경우이기 때문에 "KAKTUS"를, True가 리턴된 경우에는 dest(결과값)을 출력한다.

 

 

알게된 점

- 결과적으로 문제는 한 번에 풀 수 있었지만 자료형때문에 계속 컴파일 에러가 발생했다.

- graph[i][i]에 있는 값이 정수냐 아니냐를 판별하고 싶었는데 계속 에러가 발생했고, 노드 개수가 적기도 해서 그냥 range(200)에 포함되어 있는지 여부를 확인하는 방식으로 체크했다.

 

 

참고 사이트

-