[백준]BOJ 5558: チーズ (Cheese) - Python/BFS

5558번: チーズ (Cheese) (acmicpc.net)

5558번: チーズ (Cheese)

문제

 

+ 파파고 번역

 

풀이

처음에 문제를 읽었을 땐, 치즈를 먹는 순서를 어떻게 정해야 하나 싶었지만, 시작 할 때 쥐의 체력이 1 고정이므로 고민할 필요 없이 1, 2, 3, ..., N 순서대로 먹으면 된다.

 

BFS를 이용하여 시작 지점에서 시작해서 각 치즈간의 거리를 순서대로 더하면 된다.

코드

from collections import deque

def bfs(start, end):
    moves = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    queue = deque()
    isVisited = [[False] * w for _ in range(h)]
    queue.append((start, 0))
    isVisited[start[0]][start[1]] = True
    
    while queue:
        cur_place, cur_time = queue.popleft()
        for move in moves:
            new_place = (cur_place[0] + move[0], cur_place[1] + move[1])
            if new_place[0] < 0 or new_place[0] >= h or new_place[1] < 0 or new_place[1] >= w:
                continue
            if isVisited[new_place[0]][new_place[1]]:
                continue
            if graph[new_place[0]][new_place[1]] == "X":
                continue
            if graph[new_place[0]][new_place[1]] == end:
                return cur_time + 1
            queue.append((new_place, cur_time + 1))
            isVisited[new_place[0]][new_place[1]] = True
    return 0

h, w, n = map(int, input().split())
graph = []
for _ in range(h):
    graph.append(list(input()))

cheese_mapping = {}
for row in range(h):
    for column in range(w):
        if graph[row][column] in ["1", "2", "3", "4", "5", "6", "7", "8", "9"]:
            cheese_mapping[graph[row][column]] = (row, column)
        if graph[row][column] == "S":
            cheese_mapping["0"] = (row, column)
answer = 0
for cheese in range(1, n + 1):
    answer += bfs(cheese_mapping[str(cheese - 1)], str(cheese))

print(answer)