[백준 / Python] 9205 - 맥주 마시면서 걸어가기

알게된 것

1. 다익스트라 알고리즘: 하나의 정점에서 다른 모든 정점으로의 최단 거리 구하기
2. 플로이드 와샬 알고리즘: 모든 정점에서 모든 정점으로의 최단 경로 구하기, 거쳐가는 정점을 기준으로 최단 거리를 구한다.
   1. 참고 블로그 
   2. https://mygumi.tistory.com/110
   3. https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F
3. 이번 문제에서는 '플로이드 와샬 알고리즘'을 이용한다.
4. BFS로도 풀 수 있다고 한다.
5. 맨처음에는 BFS도 아닌, 플로이드도 아닌, 단순하게 각각의 거리를 비교하는 방식으로 풀었는데, 도저히 아닌 것 같아서 풀이를 검색해서 해결했다! 너무 모르겠으면 검색하자!
6. 모두 탐색을 한다는 생각으로 풀자. 알고리즘적인 생각이 아직 안잡혀있어서 각각의 정점만 비교하는 방식으로 처음에 생각한듯 하다.

결과

• 메모리: 124308 KB
• 시간: 312 ms

풀이과정

• 집(0) 편(1) 편(2) 페(3)
• 집(0)
• 편(1)
• 편(2)
• 페(3)

1. 이렇게 배열을 만든 후, 각각의 거리를 계산해서 1000 이하면 간선이 이어진걸로 한다.
2. 플로이드 와샬 알고리즘으로 거쳐가는 정점을 기준으로 최단 거리를 구한다.
3. 0 < 배열[집][페] < max 면 갈 수 있다는 뜻이므로 happy를 출력한다.

제출 코드

max = 1000

t = int(input()) # 1 <= t <= 50
for _ in range(t):
    n = int(input()) # 0 <= n <= 100
    homeX, homeY = map(int, input().split())
    stores = []
    for _ in range(n):
        storeX, storeY = map(int, input().split())
        stores.append((storeX, storeY))
    festivalX, festivalY = map(int, input().split())

    graph = [[max] * (n + 2) for _ in range(n + 2)]
    arr = [(homeX, homeY)]
    arr.extend(stores)
    arr.append((festivalX, festivalY))

    # 정점 간 이동 가능 표시
    for i in range(n + 2):
        for j in range(n + 2):
            if i == j:
                graph[i][j] = 0
                continue
            x1, y1 = arr[i]
            x2, y2 = arr[j]
            dist = abs(x1 - x2) + abs(y1 - y2)
            if dist <= 1000:
                graph[i][j] = 1

    for k in range(n + 2):
        for i in range(n + 2):
            for j in range(n + 2):
                if graph[i][k] + graph[k][j] < graph[i][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]

    if 0 < graph[0][n +1] < max:
        print('happy')
    else:
        print('sad')

테스트용 코드

max = 1000

# n = 2
# homeX, homeY = 0, 0
# stores = [(1000, 0), (1000, 1000)]
# festivalX, festivalY = 2000, 1000

n = 2
homeX, homeY = 0, 0
stores = [(1000, 0), (2000, 1000)]
festivalX, festivalY = 2000, 2000

graph = [[max] * (n + 2) for _ in range(n + 2)]
arr = [(homeX, homeY)]
arr.extend(stores)
arr.append((festivalX, festivalY))

# 정점 간 이동 가능 표시
for i in range(n + 2):
    for j in range(n + 2):
        if i == j:
            graph[i][j] = 0
            continue
        x1, y1 = arr[i]
        x2, y2 = arr[j]
        dist = abs(x1 - x2) + abs(y1 - y2)
        if dist <= 1000:
            graph[i][j] = 1

for k in range(n + 2):
    for i in range(n + 2):
        for j in range(n + 2):
            if graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = graph[i][k] + graph[k][j]
print(graph)

if 0 < graph[0][n +1] < max:
    print('happy')
else:
    print('sad')

참고: 플로이드 와샬 알고리즘

• 참고 블로그: https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F

n = 4
max = 1000
graph = [
    [0, 5, max, 8],
    [7, 0, 9, max],
    [2, max, 0, 4],
    [max, max, 3, 0]
]
print(graph)    

for k in range(n):
    for i in range(n):
        for j in range(n):
            if graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

print(graph)