1976 - 여행 가자

info

• 문제 보기: 1976 - 여행 가자
• 소요 시간: 29분 26초
• 풀이 언어: python
• 체감 난이도: 2️⃣~3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

bfs

풀이 코드

info

• 메모리: 34968 KB
• 시간: 68 ms

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

n, m = 0, 0
adj, plan = [], []
visited = []

def bfs(i):
    q = deque()
    q.append(i)
    visited[i] = True
    
    while q:
        cur = q.pop()
        for nxt in range(n):
            if adj[cur][nxt] and not visited[nxt]:
                q.append(nxt)
                visited[nxt] = True


def solution():
    global n, m, adj, plan, visited
    
    n = int(input())
    m = int(input())
    
    for _ in range(n):
        adj.append(list(map(int, input().split())))
        
    plan = list(map(int, input().split()))
    visited = [False] * n
    
    bfs(plan[0]-1)
    
    for city in plan:
        if visited[city-1] == False:
            print("NO")
            return
        
    print("YES")


if __name__ == '__main__':
    solution()

풀이 해설

주어진 여행 계획의 루트 노드부터 그래프 순회를 하여 한 번 쭉 스캔하는 방식으로 방문처리를 하고

여행 계획에 포함된 도시가 방문처리 되어있는지 확인하면 되는 문제

루트 노드부터 한붓그리기가 되는지 여부를 확인하면 된다.

메모

• 도시의 수 N 값의 범위가 꽤나 작은 것을 통해 bfs를 의심해볼 수 있음