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

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

내코드

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

def BFS(a,b):
    dq = deque()
    dq.append((a,b))

    while dq:
        x,y = dq.popleft()
        if abs(x-end[0]) + abs(y - end[1]) <= 1000: # ! 맥주병 20개로 갈 수 있는 최대 거리 1000
            return True
        for i in range(n): # ! 현재 위치로부터 방문 안했는지 확인
            nx,ny = store[i]
            if not visited[i]:
                if abs(x-nx) + abs(y-ny) <= 1000: # ! 맥주병 20개로 이동 가능한지
                    dq.append((nx,ny))
                    visited[i] = True
    else:
        return False


T = int(input())
for t in range(1,T+1):
    n = int(input())
    start = list(map(int, input().split()))
    store = [list(map(int, input().split())) for _ in range(n)]
    end = list(map(int, input().split()))

    visited = [False] * (n+2)
    flag = BFS(start[0], start[1])

    if flag:
        print("happy")
    else:
        print("sad")

코멘트

처음에는 해당 문제를 다익스트라처럼 구현하려고 했다. 시작위치가 정해져있고, 현재 위치로부터 이동이 가능한 거리들 그리고 맥주 개수를 최대로 유지하면서 갈 수 있다면 갱신 후 큐에 삽입 후 과정 반복.

이 과정을 진행하려고 했는데 문제에서 88퍼에서 오류가 떴다.

결국. 해당 문제는 다익스트라로 풀면 안된다 -> 왜냐하면 편의점에 들렀을 때 맥주 20병을 모두 다시 채울 수 있다. 즉 맥주 편의점에 도착하는 순간 가지고 있는 맥주는 상관이 없다.

-> 따라서 해당 문제는 다익스트라가 안된다.

또한 구하고자 하는 것을 보면 도착점(페스티벌)에 도착하는지만 확인한다. 즉 연결이 가능한지만 판단하면 된다.
-> 집 -> 편의점 -> 페스티벌 까지의 맥주가 부족하지 않으면서 연결이 되어 있는지만 판단

시작지점, 편의점, 도착지점 모두 노드라고 생각하고 간선으로 연결.

결론적으로 좌표가 갱신될 때마다 현재 좌표와 도착점과의 거리가 1000이하가 된다면 (맥주 20개로 갈 수 있음) 바로 return True 로 해주면 된다.

연결이 가능한지만 판별하기 때문에 그냥 한번 방문한 곳은 다시 방문 안해도 되므로 -> visited배열로 관리해줘도 된다.
(다익으로 하면 안됐던 문제)

근데 이렇게 연결성만을 확인하고자 할 때 플로이드 워셜로도 문제 해결이 가능하다 !!

플로이드 워셜로 문제 해결

모든 지점들 사이의 최단 거리를 구하는 것이 아니라, 각 지점들 사이에 맥주를 마시면서 갈 수 있는지 없는지를 판별 -> 각 지점 사이의 거리가 1000 (맥주 20병으로 갈 수 있는 최대거리)이하인 경우에만 서로 갈 수 있다고 판별하면 된다.

1. 모든 지점 쌍 사이의 거리 무한대 초기화 + 자기 자신 거리 0으로 초기화
2. 각 지점 쌍 거리 맨해튼 거리로 계산해서 업데이트 -> 이때 1000이하만 업데이트
3. 플로이드 워셜 알고리즘 사용해서 각 지점에서 다른 지점으로 갈 수 있는지 체크

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

def floyd(g):
    n = len(g)
    INF = int(1e9)
    dis = [[INF] * n for _ in range(n)]

    for i in range(n):
        dis[i][i] = 0 # ! 자기 자신은 0

    for i in range(n):
        for j in range(n):
            if i != j:
                d = abs(g[i][0] - g[j][0]) + abs(g[i][1] - g[j][1])
                if d <= 1000: # ! 두 정점 이어짐 가능
                    dis[i][j] = d

    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis[i][j] = min(dis[i][k] + dis[k][j], dis[i][j])

    if dis[0][-1] == INF:
        return "sad"
    else:
        return "happy"

T = int(input())
for t in range(1,T+1):
    n = int(input())
    g = []
    for _ in range(n+2):
        a,b = map(int, input().split())
        g.append((a,b))
    res = floyd(g)
    print(res)

여기 코드에서

for i in range(n):
	for j in range(n):
    	if i != j:
        	d = abs(g[i][0] - g[j][0]) + abs(g[i][1] - g[j][1])
            if d <= 1000: # ! 두 정점 이어짐 가능
            	dis[i][j] = d

위 코드는 주어진 모든 좌표들이 서로 이어질 수 있는지 먼저 확인
-> 왜냐하면 기존의 플로이드 워셜 문제들과는 다르게 좌표들만 주어졌음 -> 그렇기에 먼저 이어질 수 있는 애들인지 확인해야 한다.

위와 같이 연결성만 확인할 때 플로이드 워셜을 쓸 수 있다.

BFS로 다시 풀어봄

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")

# 출발 : 상근이 -> 맥주 한 박스
# 맥주 한 박스 20개 존재
# 50m에 한 병씩 마셔야 한다.
# 편의점에 들렸을 때 20병 모두 다시 채울 수 있음

# 상근이 -> 페스티벌 가능한지 확인
# 맥주가 계속 갱신되기 때문에 다익스트라로 푸는 것이 아니라 그냥 연결성만 확인하는 BFS나 플로이드 워셜로 푼다

def BFS(startX,startY):
    global visited
    dq = deque()
    dq.append((startX,startY))
    while dq:
        x,y = dq.popleft() # 현재 좌표로부터 이동 가능한 거리로 다 이동
        if (x,y) == (endX,endY): # 도착점 도달한 경우
            return True
        for i in range(n+1):
            nx,ny = g[i]
            if not visited[i]:
                d = abs(x - nx) + abs(y - ny)
                if d <= 1000:  # 이동 가능
                    visited[i] = True
                    dq.append((nx,ny))
    return False # 안되면 끝

T = int(input())
for _ in range(T):
    n = int(input()) # 편의점 개수
    home = [list(map(int, input().split()))] # 상근이네 좌표
    g = [list(map(int, input().split())) for _ in range(n+1)] # 편의점 + 페스티벌 좌표
    endX,endY = g[-1][0], g[-1][1] # 마지막 좌표

    # 맥주 한개에 50미터
    # 20개로는 총 1000미터 갈 수 있음.
    visited = [False] * (n+1)
    res = BFS(home[0][0], home[0][1])
    if res:
        print("happy")
    else:
        print("sad")

연결성 문제 --> 방문처리!!!
자꾸 방문처리를 까먹는다. 방문체크 해주자.

플로이드 워셜 다시

import sys
from collections import deque

sys.stdin = open("input.txt", "rt")


def floyd(g):
    N = len(g) # 정점 개수
    INF = int(1e9)
    dis = [[INF] * N for _ in range(N)] # 정점 개수만큼 만들기

    # 초기화 단계. 본인으로의 거리는 0
    for i in range(N):
        dis[i][i] = 0 # 자기자신으로의 길은 0

    # 연결된 간선들을 미리 연결하고 플로이드 워셜 시작
    for i in range(N):
        for j in range(N):
            if i == j: continue # 본인으로의 거리는 x
            d = abs(g[i][0] - g[j][0]) + abs(g[i][1] - g[j][1])
            if d <= 1000: # 이동 가능
                dis[i][j] = d # 이동 가능하다는 뜻

    # 이제 초기화 : 본인으로의 거리 0처리, 연결된 간선 미리 연결. 끝났으니 진행
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    if dis[0][-1] == INF: # 시작점이 0번 인덱스 도착점이 -1. 즉 n+1인덱스!!니까
        return "sad"
    else:
        return "happy"


T = int(input())
for _ in range(T):
    n = int(input())
    g = []
    for _ in range(n+2):
        a,b = map(int, input().split())
        g.append((a,b))

    res = floyd(g)
    print(res)