💡 백준 9205:
BFS로 모든 경로를 탐색하여 도달 가능 여부 판단
🌱 코드 in Python
알고리즘: BFS
import sys
input = sys.stdin.readline
t = int(input())
def bfs():
while q:
cur_x, cur_y = q.pop(0)
if abs(e_x - cur_x) + abs(e_y - cur_y) <= 1000: # 페스티벌에 도착 가능 할 경우
return "happy"
for i in range(c): # 도중 들를 수 있는 순서와 상관 없이 편의점을 모두 탐색
if visit[i] == 0:
nx, ny = c_list[i][0], c_list[i][1]
if abs(nx - cur_x) + abs(ny - cur_y) <= 1000: # 현재 위치부터 다음 목적지의 거리가 1,000m 이상 떨어지지 않아야 함
q.append((nx, ny))
visit[i] = 1
return "sad"
for _ in range(t):
c = int(input())
x, y = map(int, input().split())
c_list = []
for _ in range(c):
c_x, c_y = map(int, input().split())
c_list.append((c_x, c_y))
e_x, e_y = map(int, input().split())
visit = [0] * c
q = []
q.append((x, y))
print(bfs())이번 문제는 이동거리가 1,000m를 넘지 않을 때만 이동하면서 목표좌표까지 이동할 수 있는 지 여부를 판단하는 문제였다
문제를 읽으면서 이러면 사실 저 칭구칭긔들이 페스티벌에 도착하기 전에 급성 알콜 중독으로 사망하는 것이 먼저가 아닐까 하는 걱정이 들긴 했지만,,
아무튼..
일단 이 문제에서 중요한 점 3가지는
1️⃣ 50m마다 1병을 마셔야 하고 최대로 가질 수 있는 맥주병은 20병이기 때문에 한 텀에 최대 1,000m 이동 가능
(나는 각 1병인 줄 알고 500m 가능한 줄 알았는데 예제보고 둘이 1병인거 깨달음.. 저걸 나눠마셔..?)
2️⃣ 편의점을 순서대로 들르는 것이 아닌, 그때 그때 가능한 경우의 수를 찾아야 함
예를 들어
3
0 0
0 2000
1000 0
0 1000
0 3000
과 같이 입력이 들어왔을 때 3->1 편의점을 거쳐 페스티벌에 도착할 수 있다
3️⃣ 거리 비교는 x, y값을 따로 + 절댓값으로 계산해야 함
뭐,, 이건 다들 아는 얘기겠지만 나는 빡대가리이므로..
첨에 편의점x + 편의점 y - x - y <= 1,000 이딴 식으로 계산했다 ^0^
하지만 문제에서 나와있듯이 좌표는 음수로도 주어질 수 있다는 것을 꼭 명심명십팝팝..
여기서 가장 내가 헤맸던 부분은 2️⃣였는데, 일단 각 편의점의 거리가 어떤 depth로 이루어진 것이 아니었기 때문에
bfs, dfs가 다 가능할거라는 생각은 들었다
근데, 어떻게 그들이 모두 연결된 경로를 찾을 수 있는거지?! 하고 여기서 막혔었다
한 편의점 정점이 모든 편의점 정점들을 탐색하며 경로를 연결연결 해서 페스티벌 장소까지 갈 수 있는지를 판단해야 했기 때문이다
그래서 😸 아 나는 dfs 같은 건 모르겠고~! bfs로 냅다 for문을 돌려야겠단 생각밖에는 못했다 ㅎㅎ
1. 처음 시작점에서 방문 가능한 == 1,000m 안에 있는 편의점 정점을 모두 큐에 추가한다
2. 추가된 편의점 정점으로 x, y 좌표를 변경한 후 방문 가능한 다른 편의점 정점을 모두 큐에 추가한다 * 반복
3. 연결된 정점에서 페스티벌에 도착이 가능한지 여부를 판단한다그렇게 완성된 로직은 위와 같다
visit[i] == 1 이라는 것은 그 정점까지 어떤 정점을 통해서 방문이 가능하단 얘기고 거기서 연결연결 해 나가면 되는 것이다
🧠 기억하자
- 오늘은 그냥 어려웠다ㅠㅠ
