Search
Duplicate

맥주 마시면서 걸어가기

주차
22
문제번호
9205
언어
Python
티어
실버
유형
플로이드-와샬
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

로직 설명

한 노드에서 다른 노드의 거리가 1000 이하라면 이동할 수 있습니다.
인접 행렬로 표현하여 플로이드-와샬을 통해 시작 노드에서 마지막 노드까지 이동할 수 있는지 확인합니다.

Code

제출 날짜

@6/6/2021
import sys t = int(sys.stdin.readline().strip()) for x in range(t): n = int(sys.stdin.readline().strip()) li = [[0 for _ in range(n+2)] for _ in range(n+2)] save = [] for i in range(n+2): a, b = map(int, sys.stdin.readline().split()) save.append((a,b)) for i in range(n+2): for j in range(n+2): if (i == j): continue if (abs(save[i][0] - save[j][0]) + abs(save[i][1] - save[j][1]) <= 1000): li[i][j] = 1 for k in range(n+2): for i in range(n+2): for j in range(n+2): if (i == j): continue if li[i][k] and li[k][j]: li[i][j] = 1 if (li[0][n+1]): print("happy") else: print("sad")
Python
복사