[백준] 5558 : Cheese (Python)

출처 : https://www.acmicpc.net/problem/5558

 

문제

올해도 JOI 마을의 치즈 공장이 치즈 생산을 시작했고, 쥐가 둥지에서 얼굴을 냈다. 쥐는 둥지에서 출발해 모든 치즈 공장을 방문해 치즈를 1개씩 먹는다.

이 마을에는 N개의 치즈 공장이 있으며, 각 공장은 1종류의 치즈만을 생산한다. 치즈 공장은 하나씩만 존재한다.

쥐의 초기 체력은 1이며, 치즈를 1개씩 먹을 때마다 체력이 1증가한다.

쥐는 동서남북에 인접한 구역으로 1분에 이동할 수 있지만, 장애물 지역에는 들어갈 수 없다. 모든 치즈를 먹기까지 걸리는 최단 시간을 요구하는 프로그램을 작성하시오.

입력

입력은 H+1행이다. 2행에서 H+1행까지의 각 행은 'S','1','2',...,'9','X','.'로 구성된 W문자의 문자열이 써져 있으며, 각각이 각 구역의 상태를 나타낸다. 

출력

모든 치즈를 먹기까지 걸리는 최단 시간을 나타내는 정수를 출력하라.

 

---

 

아이디어

해당 문제는 미로 탐색과 같은 유형이다. 그래프 탐색 기법인 BFS를 통해 상하좌우를 체크할 수 있다. 그렇다면, 분기점이 어떻게 나뉘는지에 대해 생각해보자.

분기점이 나뉘는 경우의 수는 다음과 같다.

1. 치즈를 먹지 않고 지나가는 경우
2. 치즈를 먹고 지나가는 경우
3. 치즈를 먹고 돌아가는 경우

이 세가지 경우를 그래프 그림으로 표현하면 다음과 같다.

세가지 경우에 대한 분기점을 표현한 그래프

 

해당 그래프 그림을 통해 치즈 구역인 경우 분기점이 3개가 추가되고, 각 경우에서 동서남북으로 나뉘게 되는 것을 알 수 있다. 즉, 한번의 그래프 탐색에서 3개의 추가되는 분기점은 거듭제곱 형식이므로, 메모리 & 시간 측면에서 매우 비효율적이다.

그러므로, 탐색을 다른 방식으로 생각해보아야 한다.

다시 말해, 완전 탐색은 시간이 많이 걸릴 수 밖에 없다. BFS는 최단 경로를 보장하는 탐색 기법이다. 이 특징을 활용한다면, 목표점까지 도달하는 레벨(그래프 깊이)까지만 탐색을 진행하면 된다.

결국, 탐색 방식에 따른 인사이트는 다음과 같다.

분기점 추가와 고정된 시작점 ~ 목표점까지 해당되는 사이클의 반복 비교

이를 시각화하여 확인해보자.

시작점~목표점 사이클 탐색

 

해당 그래프를 통해 다음과 같은 탐색 알고리즘을 구현할 수 있다.

• 쥐는 치즈의 경도 순으로 먹을 수 밖에 없다. (1->2->...->N)
• 1 ~ N까지 각각 그래프 탐색의 목표점으로 설정하여 BFS 진행
• 첫 시작점은 둥지이며, 목표점에 도달할 시마다, 시작점과 목표점을 갱신하여 다음 탐색 진행
• 시작점 ~ 목표점까지의 거리를 계속해서 갱신.

 

정답 코드

# https://www.acmicpc.net/problem/5558
# Cheese
# 그래프 탐색

deque=__import__('collections').deque
input=__import__('sys').stdin.readline

def bfs(starts,targets):
    q=deque([starts])
    visited=[[0]*w for _ in range(h)] # 방문여부 및 거리(시간)저장
    visited[starts[0]][starts[1]]=1
    
    while q:
        x,y=q.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if 0<=nx<h and 0<=ny<w:
                # 목표점 도달
                if (nx,ny)==targets:
                    return visited[x][y]
                # 빈칸이거나 치즈인 경우에서 미방문한 칸이면.(치즈의 경우 목표 치즈가 아닌 경우)
                if (board[nx][ny] in ['.','S'] or board[nx][ny].isdigit()) and visited[nx][ny]==0:
                    visited[nx][ny]=visited[x][y]+1
                    q.append((nx,ny))
    
    return 0

h,w,n=map(int,input().split())
visited=[[0]*w for _ in range(h)]
board,start_idx,cheese_idxs=[],(),[() for _ in range(n+1)]
total_distance=0

start_idx_flag=True
for i in range(h):
    tmp=[*input()][:-1]
    for j in range(w):
        if start_idx_flag and tmp[j]=='S':
            start_idx=(i,j)
            start_idx_flag=False
        if tmp[j].isdigit():
            cheese_idxs[int(tmp[j])]=(i,j)
    board.append(tmp)

dx=[-1,1,0,0]
dy=[0,0,-1,1]

# 치즈 1~N까지 순차적으로 BFS 탐색.
for idx in range(1,n+1):
    total_distance+=bfs(start_idx,cheese_idxs[idx]) # 현재 시작점~현재 치즈까지의 거리(시간) 갱신
    start_idx=cheese_idxs[idx] # 다음 탐색 시작점 갱신

print(total_distance)