[백준] 24444, 24445, 24479, 24480 - 알고리즘 수업

문제 설명

24444
24445
24479
24480

DFS와 BFS를 다루는 기본 문제들이다. 이분 탐색과 같이 기본기부터 연습하고 유형에 익숙해지고자 위 네 문제를 선택했다.

24444

인접한 정점이 두 개 이상이면 오름차순으로 방문한다는 점과, 방문한 순서로 출력하는 것이 아닌, n번째 노드를 몇 번째로 방문했는지 n번째 줄에 출력하는 것이 포인트이다.

24445

24444와 같은 문제이나, 방문을 노드 번호의 내림차순으로 한다는 차이가 있었다. 다만, 연습을 위했던 것이어서 복사 붙여넣기가 아닌 직접 작성으로 다시 풀어보았다.

24479

같은 문제이나 DFS로 탐색해야 한다. 스택으로 구현했다.

24480

24445와 같이 내림차순으로 DFS구현을 해야 하는데, DFS는 재귀와 스택으로 구현이 가능하며, 24479를 스택으로 구현하였기에 이 문제는 재귀로 구현했다.

코드

24444:

import sys
from collections import deque

input = sys.stdin.readline

def bfs(start, arr):
    queue = deque()
    queue.append(start)
    order = 1

    while queue:
        now = queue.popleft()
        if visited[now] == 0:
            visited[now] = order
            order += 1
            for node in arr[now]:
                if visited[node] == 0:
                    queue.append(node)
            

N, M, R = map(int, input().split())

adj = [[] for _ in range(N+1)]
visited = [0] * (N+1)
ans = [0 * (N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

for start in adj:
    start.sort()

bfs(R, adj)

for i in range(1, N+1):
    print(visited[i])

24445

import sys
from collections import deque

input = sys.stdin.readline

def bfs(start, arr):
    queue = deque()
    queue.append(start)
    order = 1

    while queue:
        now = queue.popleft()
        if visited[now] == 0:
            visited[now] = order
            order += 1 
            for node in arr[now]:
                if visited[node] == 0:
                    queue.append(node)

N, M, R = map(int, input().split())

adj = [[] for _ in range(N+1)]
visited = [0] * (N+1)

for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

for start in adj:
    start.sort(reverse=True)

bfs(R, adj)

for i in range(1, N+1):
    print(visited[i])

24479

import sys
input = sys.stdin.readline

def dfs(start, arr):
    stk = []
    stk.append(start)
    order = 1

    while stk:
        now = stk.pop()
        if visited[now] == 0:
            visited[now] = order
            order += 1 
            for node in adj[now]:
                if visited[node] == 0:
                    stk.append(node)


N, M, R = map(int, input().split())

adj = [[] for _ in range(N+1)]
visited =[0] * (N+1)

for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

for start in adj:
    start.sort(reverse=True)

dfs(R, adj)

for i in range(1, N+1):
    print(visited[i])

24480

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

def dfs(start, arr):
    global order
    visited[start] = order
    order += 1

    for node in arr[start]:
        if visited[node] == 0:
            dfs(node, arr)

N, M, R = map(int, input().split())

adj = [[] for _ in range(N+1)]
visited =[0] * (N+1)

for _ in range(M):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

for start in adj:
    start.sort(reverse=True)

order = 1 

dfs(R, adj)

for i in range(1, N+1):
    print(visited[i])