문제
송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.
상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.
편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)
각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).
다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)
송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)
출력
각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나서 더 이동할 수 없으면 "sad"를 출력한다.
예제입력
2
2
0 0
1000 0
1000 1000
2000 1000
2
0 0
1000 0
2000 1000
2000 2000
예제출력
happy
sad
풀이방법
이 문제는 그래프 탐색이론이다. 이 문제는 BFS로 풀었다.
시작 지점을 먼저 큐에 넣고 그 다음 받는 편의점의 좌표들을 방문해야 할 노드들로 판단한다. 이때 방문 가능한 조건은 위에서 말한 20*50이하의 거리에 있는 좌표여야 한다.
이를 위해 현재에서 x의 격차와 y의 격차의 합이 1000을 넘지 않는 곳이면서 이전에 방문하지 않았을 경우 큐에 넣어서 방문하는 것으로 구현했다.
코드
from collections import deque
T=int(input())
for _ in range(T):
n=int(input())
q=deque()
check=True ##bfs도중 성공했는지 체크
a,b=map(int,input().split(' '))
q.append([a,b])#시작지점을 먼저 큐에 넣는다
con=[]#편의점의 좌표들 및 페스티벌 좌표
visited=[]
for _ in range(n+1):#편의점 좌표와 페스티벌 좌표를 넣는다
a,b=map(int,input().split(' '))
con.append([a,b])
visited.append(0)
while(len(q)!=0):#bfs
now=q[0]
q.popleft()
if(con[-1][0]==now[0] and con[-1][1]==now[1]):#만약 현재 지점이 페스티벌 장소면
print('happy')#해피출력
check=False#출력완료를 체크 한 후
break#bfs종료
for i in range(n+1):#아닐경우 노드 전체에서 방문 가능한 노드를 찾는다
if(visited[i]==0 and (abs(now[0]-con[i][0])+abs(now[1]-con[i][1]))<=1000):
visited[i]=1
q.append([con[i][0],con[i][1]])
if(check):#해피를 출력 못했으면
print('sad')#못가는 거니까 슬퍼
후기
쉬운 그래프 탐색 문제였다. 그래프 탐색 문제들이 전반적으로 이제는 쉽게 다가온다. 그래프 문제들은 빨리 마스터 하고 더 다양한 문제들을 풀어야지
