파이썬 백준 9205번 : 맥주 마시면서 걸어가기

문제 

https://www.acmicpc.net/problem/9205

 

 

🍺풀이

자료구조 

이차원 리스트를 활용해서 집, 편의점, 페스티벌의 좌표를 저장했다. 

visited함수는 set에 튜플을 저장했다. 

알고리즘 

BFS를 사용했다. 

import sys
from collections import deque

def move():
    queue=deque()
    queue.append(maps[0]) #집을 queue에 넣음
    visited.add(tuple(maps[0])) #방문처리
    while(queue):
        x,y=queue.popleft() 
        visited.add((x,y)) #방문처리
        if x==maps[n+1][0] and y==maps[n+1][1]: #페스티벌 도착시 happy 반환
            return "happy" 
        for maps_x, maps_y in maps: #maps안의 좌표(편의점, 페스티벌 위치)를 순회
            if (maps_x,maps_y) not in visited and abs(maps_x-x)+abs(maps_y-y)<=1000: #방문하지 않고, 갈수 있는 곳이라면(이동거리 1000m이하)
                queue.append([maps_x,maps_y]) #queue에 넣음
    return "sad" #페스티벌 도착 못할 시 sad반환 

t=int(sys.stdin.readline())
for _ in range(t):
    maps=[] #좌표를 담을 리스트
    visited=set() #방문체크를 위한 set
    n=int(sys.stdin.readline())
    for _ in range(2+n): #집+페스티벌+n(편의점개수)만큼 maps에 넣음
        maps.append(list(map(int,sys.stdin.readline().split())))
    print(move())

 

 

 

 

 

😣덧) 처음에 3%에서 틀렸는데 한방향으로만 갈수 있다고 착각해서 풀었기 때문이었다..

 

'''
반례
1
0
0 0
500 500
'''

import sys
from collections import deque

def move():
    queue=deque()
    queue.append(maps[0])
    visited.add(tuple(maps[0])) #방문처리
    while(queue):
        x,y=queue.popleft()
        visited.add((x,y)) #방문처리
        if x==maps[n+1][0] and y==maps[n+1][1]: #페스티벌 도착
            return "happy"
        for i in range(4):
            new_x=x+dx[i]
            new_y=y+dy[i]
            for maps_x, maps_y in maps:
                if (maps_x,maps_y) not in visited and abs(new_x)>=abs(maps_x) and abs(new_y)>=abs(maps_y):
                    queue.append([maps_x,maps_y])
    return "sad"



dx=[-1000,1000,0,0]
dy=[0,0,1000,-1000]
t=int(sys.stdin.readline())
for _ in range(t):
    maps=[]
    visited=set()
    n=int(sys.stdin.readline())
    for _ in range(2+n):
        maps.append(list(map(int,sys.stdin.readline().split())))
    print(move())