[백준-9372] 상근이의 여행

문제

링크

코드

import sys
from collections import deque
input = sys.stdin.readline
t = int(input())


def bfs(n, graph) :
    global answer
    queue = deque()
    queue.append(n)
    visit[n] = 1
    while queue :
        if 0 not in visit :
            break
        n = queue.popleft()
        for g in graph[n] :
            if visit[g] != 1 :
                queue.append(g)
                visit[g] = 1
                answer += 1
            
            
for _ in range(t) :
    n, m = map(int, input().split())
    answer = 0
    graph =[[] for _ in range(n+1)]
    visit = [0] * (n+1)
    visit[0] = 1
    for _ in range(m) :
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
    bfs(1, graph)
    print(answer)

풀이

일단 문제는 bfs를 이용하여 풀었다.

상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다.

저 부분을 잘 이해하지 못하고 방문처리를 하지 않았다. 그랬더니 틀렸고, 다시 방문처리를 하니까 정답처리가 됐다.