구름 먼데이 챌린지 참여하기

문제

입력

출력

예제

• 입력1

6 6 2
1 4
4 2
2 6
4 3
1 2
3 1

• 출력1

YES

• 입력2

6 6 2
1 2
2 3
3 4
3 5
5 6
5 2

• 출력2

NO

• 입력3

3 1 1
1 2

• 출력3

NO

풀이

문제 보고 아.. BFS인건 알겠다 했는데 못 풀었다. 난 언제쯤.. 코테 문제를 잘 풀 수 있게 될까.............힘내자

defaultdict를 이용해 인접리스트를 구현한다. <섬번호: 해당 섬과 연결된 섬들의 번호리스트>의 형태로 저장한다.
queue를 이용해 다음에 방문할 섬 번호를 저장한다. 앞에서부터 하나씩 꺼내서 섬을 방문한다.
BFS 방식으로 탐색한다.
visited 리스트를 두어 다리를 몇 번 건너서 해당 섬에 도착했는지 저장한다.

파이썬 코드

import sys
input = sys.stdin.readline
from collections import deque
from collections import defaultdict

n, m, k = map(int, input().split())
dict = defaultdict(list)  # graph
for i in range(m):  # 인접리스트 구현
    s, e = map(int, input().split())
    dict[s].append(e)
    dict[e].append(s)
# print(dict)

q = deque()
# 건너는 다리 갯수 visited, -1로 채움
visited = [-1 for _ in range(n+1)]
visited[1] = 0  # 1번 노드 시작이므로 0으로 바꾸고 queue에 추가(한 번 방문)
q.append(1)

# q는 탐색 후보 노드들이니, 탐색 후보가 없다면 반복문 종료
while q:
    cur = q.popleft()
    for next in dict[cur]:
        if visited[next] != -1:
            continue
        q.append(next)
        visited[next] = visited[cur] + 1

# print(visited)
# 한 번도 방문하지 않은 경우가 있을 수 있으니 1이상
if 1 <= visited[n] <= k:
    print("YES")
else:
    print("NO")