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

골드 5 - https://www.acmicpc.net/problem/9205

Code

from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

t = int(input())

def get_dist(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

def bfs(q):
    q.append(home)
    while(q):
        curr = q.popleft()
        x = curr[0]
        y = curr[1]

        if(get_dist(x, y, fest[0], fest[1]) <= 1000):
            print("happy")
            return

        for i in range(n):
            if(visited[i] == 0):
                dist = get_dist(x, y, conv[i][0], conv[i][1])
                if(dist <= 1000):
                    q.append(conv[i])
                    visited[i] = 1
    print("sad")
    return

for _ in range(t):
    n = int(input())
    home = list(map(int, input().split()))
    conv = [list(map(int, input().split())) for _ in range(n)]
    fest = list(map(int, input().split()))

    q = deque()

    visited = [0 for i in range(n+1)]
    bfs(q)

풀이 및 해설

• 헤맨 포인트
  • 거리 계산할 때 dist // 50 ≤ 20 조건으로 했다가 계속 틀렸는데 아무리 정답 코드 봐도 나랑 다 똑같은데 이 조건만 달랐음
    근데 dist ≤ 1000 으로 바꾸니까 바로 정답됨 (,,,ㅇㄴ)
  • 편의점 방문 순서가 입력으로 들어온 순서가 아니어도 된다는 점

    • 집 → 2번 편의점 먼저 방문 이런식으로 해서 만약 맥주가 안부족하게 도달할 수 있다면 정답처리

      1
      2
      0 0
      1000 1000
      1000 0
      2000 1000
      
      >>> 정답 : "happy"

  • “sad” 출력을 flag를 사용하지 않아도 됨 (해당 조건에 들어갔을때 flag 거는게 더 애매함 + 예외가 존재)