[DFS/BFS/완전탐색] ★ 9205번 - 맥주 마시면서 걸어가기(BFS)

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

풀이 시간: 90분 이내

 

1) 문제 해결 아이디어

이 문제는 방향벡터(dx, dy)등을 이용하여 최단 경로를 찾는 문제가 아니기때문에 편협한 사고방식으로는 BFS로 풀어야겠다고 바로 떠올리기가 쉽지 않은 문제였다. 추후 복습이 꼭 필요한 문제!

오늘의 교훈: 방향벡터를 사용하지 않는 문제도 BFS로 풀 수 있다!!

 

처음에는 단순하게 각 좌표들을 x, y 기준 오름차순으로 정렬하고 for문을 돌려서 현재 지점과 다음 지점의 거리(x 좌표의 차이 + y 좌표의 차이)가 1000이 넘으면 바로 종료하게 설계했다. 그런데 생각해보니 그렇게 정렬을 하면 오류가 있다는 사실을 알아냈다.

 

예를 들어, 아래와 같이 입력받았다고 하자.

현재 지점: (0, 0)

편의점: (500, 600), (600, 400)

끝 점: (1000, 10000)

 

정렬기준에 따라 (500, 600)을 먼저 수행하는데 그렇게 되면 시작점과 거리가 1100이 되므로 바로 종료하게 된다. 하지만 실제로는 (0, 0) >> (600, 400) >> (1000, 1000) 순서로 가면 거리가 모두 1000이하이므로 성공하게 된다. 이렇듯이 단순히 정렬을 해서는 풀 수 없는 문제이고 BFS를 돌려 하나하나 확인하는 방식으로 해결해야한다고 생각했다.

 

<동작 과정>

1. 편의점 방문 여부를 검사하는 visited를 0으로 초기화하여 생성한다.

2. 시작점 큐에 삽입

3. 편의점 탐색

3-1. 큐에서 편의점 좌표 1개 꺼내기

3-2. 꺼낸 좌표와 목표 좌표(end) 사이의 거리가 1000이하면 True 리턴

3-3. 꺼낸 좌표와 목표 좌표(end) 사이의 거리가 1000보다 크면 편의점 탐색 시작

3-4. 탐색할 편의점에 방문하지 않았고 거리가 1000이하이면 큐에 삽입, 방문 처리

4. 3-2 조건을 만족하지 않았으면 False 리턴

 

Q. 지점 간 거리가 1000이하인지를 검사하는 이유는?

지점 간 거리 =  x 좌표의 차이 + y 좌표의 차이

50m당 맥주 1병이 필요한데, 최대 보유가능한 맥주가 20병이므로 총 50 * 20 = 1000m 만큼 이동이 가능하다. 그 이상의 거리는 어떻게 해도 이동이 불가하다.

 

2) 소스코드

from collections import deque

# BFS
def bfs():
  queue = deque()
  # 시작점 삽입
  queue.append((start[0], start[1]))

  while queue:
    x, y = queue.popleft()
    # 끝점과의 거리가 1000이하이면 성공(탈출 조건)
    if(abs(x - end[0]) + abs(y - end[1]) <= 1000):
      return True

    for i in range(n):
      # 방문한적이 없고
      if(visited[i] == 0):
        # 거리가 1000이내이면 삽입, 방문 처리
        if(abs(x - graph[i][0]) + abs(y - graph[i][1]) <= 1000):
          queue.append((graph[i][0], graph[i][1]))
          visited[i] = 1
  return False

t = int(input())  # 테스트 케이스 수
for _ in range(t):
  res = True  # 여부
  n = int(input())  # 편의점 개수
  start = list(map(int, input().split())) # 시작점
  graph = [list(map(int, input().split())) for _ in range(n)]  # 편의점
  end = list(map(int, input().split())) # 끝점
  visited = [0] * (n + 1)  # 편의점 방문 여부
  
  res = bfs()
  if res:  print("happy")
  else:  print("sad")

[참고] https://letalearns.tistory.com/96

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