[BOJ/백준] 1260 DFS와 BFS

from collections import deque


def dfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    stack = [V - 1]
    
    while stack:
        x = stack.pop()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N - 1, -1, -1):
            if graph[x][k] >= 1:
                graph[x][k] = 0
                graph[k][x] = 0
                stack.append(k)
    
    return result


def bfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    q = deque()
    q.append(V - 1)

    while q:
        x = q.popleft()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N):
            if graph[x][k] >= 1:
                graph[x][k] -= 1
                graph[k][x] -= 1
                
                q.append(k)
    
    return result



N, M, V = map(int, input().split())
arr = [list(map(int ,input().split())) for _ in range(M)]

dfs_res = dfs()
for i in range(len(dfs_res)):
    print(dfs_res[i], end=" ")
print()
bfs_res = bfs()
for i in range(len(bfs_res)):
    print(bfs_res[i], end=" ")
print()

DFS와 BFS 문제이다.

 

웹개발 중 코테 대비하면서 연습용으로 오랜만에 풀었던 문제라, 코드가 별로이다.

 

 

def solution(start,flag):
    global N
    stack = [start]
    visited = [True]*(N+1)
    ind = 0
    if flag:
        ind = -1
    result = []
    while stack:
        node_number = stack.pop(ind)
        if not visited[node_number]:
            continue
        visited[node_number] = False
        result.append(node_number)
        for next_node in sorted(graph[node_number],reverse=flag):
            if visited[next_node]:
                stack.append(next_node)
    return result




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


graph = [[] for _ in range(N+1)]

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



print(*solution(V,True))
print(*solution(V,False))

 기본적인 풀이는 같다. DFS이냐, BFS이냐에 따라 트리거를 주었고, DFS일때는 pop하는 index를 -1로 아니면 0으로 주었다.

 

그리고 dfs는 뒤에서부터 pop이 되므로, graph를 내림차순으로 정렬해주고, bfs는 오름차순으로 정렬해주는것만 다르다.