| def BFS(E) : que = [E] while que : a, b = que[0][0], que[0][1] del que[0] for c in C : if c[2] == 0 : if abs(c[0] - a) + abs(c[1] - b) <= 1000 : c[2] = 1 que.append(c) testcase = int(input()) for t in range(testcase) : n = int(input()) C = [] H = list(map(int, input().split())) + [1] for i in range(n+1) : C.append(list(map(int, input().split())) + [0]) BFS(H) if C[n][2] == 1 : print("happy") else : print("sad") |
맥주 20병을 들고다니면서 50m마다 마시는 미친사람이 있어서 쫄았다.
다행히도 그냥 1000m 갈때마다 주유를 해줘야 한다는 의미였다.
거리가 1000 이하면 연결된 것으로 취급하여 que에 재등록하는 BFS 탐색을 정의했다.
홈 H, 편의점 c, 락페 C[n]라는 각각의 위치에 대해 [x좌표, y좌표, 발자국(0or1)]을 받고, BFS를 H에서 실행한다.
C[n]에 발자국이 찍혔다면 H와 C[n]이 연결된 것이므로 happy
찍히지 않았다면 연결되지 않은 것이므로 sad를 출력한다.
'Week 01 ~ 04 : 알고리즘 문제 풀이' 카테고리의 다른 글
| 파이썬 백준 6603 로또 (0) | 2021.11.11 |
|---|---|
| 파이썬 백준 1924 2007년 (0) | 2021.11.11 |
| 파이썬 백준 17478 재귀함수가 뭔가요? (0) | 2021.11.10 |
| 파이썬 백준 2748 피보나치 수 2 (0) | 2021.11.10 |
| 파이썬 백준 2468 안전 영역 (0) | 2021.11.09 |