우주의 IT 소행성

나의 코드

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
result = [0] * (n + 1)
count = 1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

data = [r]
while data:
    cur = data.pop(0)
    visited[cur] = True
    result[cur] = count
    count += 1

    for i in sorted(graph[cur], reverse=True):
        if not visited[i]:
            visited[i] = True
            data.append(i)

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

http://noj.am/24444 

너비우선탐색 1 문제에 reverse=True 옵션을 추가하여 내림차순으로 bfs

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
result = [0] * (n + 1)
count = 1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

data = [r]
while data:
    cur = data.pop(0)
    visited[cur] = True
    result[cur] = count
    count += 1

    for i in sorted(graph[cur]):
        if not visited[i]:
            visited[i] = True
            data.append(i)

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

나의 코드

bfs로, 이전 dfs와 다르게 재귀가 아닌 반복으로 풀었다.

주어진 데이터 수가 작아 리스트 자료형을 사용했으나 방대해진다면 deque를 불러와 popleft를 사용하는것이 유리

import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
count = 1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)


def dfs(r):
    global count
    visited[r] = count
    graph[r].sort(reverse=True)

    for i in graph[r]:
        if visited[i] == 0:
            count += 1
            dfs(i)

dfs(r)
for i in visited[1:]:
    print(i)

오름차순 -> 내림차순으로 변경된 변형문제

내 코드

import sys
sys.setrecursionlimit(10 ** 5)
input = sys.stdin.readline

n, m, r = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)
count = 1

for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

for i in graph:
    i.sort()

def dfs(r):
    global count
    visited[r] = count

    for i in graph[r]:
        if visited[i] == 0:
            count += 1
            dfs(i)

dfs(r)
print(*visited[1:], sep="\n")

보편적인 recursion dfs 방식으로 해결

메모리 초과 오류가 난다면 setrecursionlimit을 10 ** 4로 설정