[BOJ 9205] 맥주 마시면서 걸어가기 (Python3)

 

 

www.acmicpc.net/problem/9205

9205번: 맥주 마시면서 걸어가기

 

 

from collections import deque

t=int(input())
INF=int(1e9)

for _ in range(t):
    flag=0
    n=int(input())
    graph=[[INF]*(n+3) for _ in range(n+3)]
    array=[[] for _ in range(n+3)]
    visited=[False]*(n+3)
    l=[()]
    for a in range(1,n+3):
        for b in range(1, n+3):
            if a==b:
                graph[a][b]=0
    for _ in range(n+2):
        x,y=map(int, input().split())
        l.append((x,y))
    for i in range(1,n+3):
        for j in range(i, n+3):
            dist=abs(l[i][0]-l[j][0])+abs(l[i][1]-l[j][1])
            graph[i][j]=dist
            graph[j][i]=dist
    
    for k in range(1, n+3):
        for a in range(1, n+3):
            for b in range(1, n+3):
                graph[a][b]=min(graph[a][b], graph[a][k]+graph[k][b])
    
    for a in range(1,n+3):
        for b in range(1, n+3):
            if 0<graph[a][b]<=1000:
                array[a].append(b)

    queue=deque([1])
    visited[1]=True
    while queue:
        v=queue.popleft()
        for i in array[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True

    if visited[n+2]==True:
        print("happy")
    else:
        print("sad")

 

1. 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)으로 모든 지점에서 다른 모든 지점까지의 최단 경로를 구한다.

2. BFS 로 위치A-위치B의 거리가 0 보다 크고 100보다 작거나 같은 것을 인접 탐색 노드로 삼는다.

3. BFS 로 방문할 때, 목적지 노드를 방문하였다면 happy를 출력한다. 아니면 sad를 출력한다.

 

개인적으로 플로이드 워셜, BFS 라는 힌트가 없었다면 풀기가 어려운 문제였다.

플로이드 워셜로 각 지점 간 최단거리 구하다가, 탐색을 어떻게 해야할지 고민했는데..답은 BFS 였다!!

아 이럴때도 BFS 를 사용할 수 있구나!!!!! 너무 정형화된 사고방식을 한것 같다 ㅠㅠ 

 

플로이드 워셜로 일단 최단거리를 구한 뒤, 거리가 1000 이하인 노드에 한해서만(그래야 움직일 수 있다) 해당 노드의 인접 노드로 설정해 준다. 인접 노드로 설정해 주었다면, 이를 BFS로 탐색하여 목적지 노드를 방문하였는지 체크하면 된다.

 

두가지 알고리즘이 섞여서 나에겐 challenge였다.

인접을 탐색할 때 or 탐색이 필요할 때 BFS를 생각해보자.