백준 24444 알고리즘 수업 - 너비 우선 탐색 1 - 실버2 [파이썬]

https://www.acmicpc.net/problem/24444

24444번: 알고리즘 수업 - 너비 우선 탐색 1

 

[실패] 라고 떠있길래 이걸 왜못풀었지? 싶었는데 못푼 이유가 있었다.

시간복잡도를 상당히 신경써야 하는 문제...

그냥 대충 행렬로 만들면 안됐다.

 

이전에 자바로 [실패] 를 엄청 많이 했길래 이걸 못풀었어? 하고 슥 풀라했다가

이번에도 [실패] 난무했다.

 

항상 풀던대로 visited 를 이용해줬는데,

얘를 빼고 풀어보니 통과가 됐다.

그리고 answer 리스트에 답을 담는 과정에서 불필요하게 if문이 도는걸 막았다.

 

import sys
from collections import deque
input = sys.stdin.readline
N, M, R = map(int, input().split())
graph = [[] for i in range(N+1)]
# visited = [False for i in range(N+1)]
answer = [0 for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, N+1):
    graph[i].sort()


queue = deque()
queue.append(R)
answer[R] = 1
cnt = 2
while queue:
    num = queue.popleft()
    # visited[num] = True
    # if answer[num] == 0:
    #     answer[num] = cnt
    #     cnt += 1

    for idx in graph[num]:
        if answer[idx] == 0:  # 방문한적 없으면 고
            queue.append(idx)
            answer[idx] = cnt
            cnt += 1

for i in answer[1:]:
    print(i)

# visited 이녀석 생성하는 시간이 오래걸렸나? 
# visited 역할을 answer가 대신 하게 해줬더니 통과됐다.

 

 

띠옹띠옹 오답 실화냐