백준 1260 풀이 (DFS, BFS, 그래프 탐색)

이번 문제는 그래프 탐색 문제이다. 그래프가 주어지면 이것을 DFS,BFS방식으로 탐색하여 순서를 나타내면 된다. 

DFS, BFS의 개념은 알고 있었지만 막상 코딩으로 짜려니 상당히 헤매었다.

 

DFS를 설명하자면 깊이 우선 탐색방법으로 깊게 들어가는 가며 탐색하는 방법이다 원리는 구글에 자세히 나온다.

처음 도움을 받은 곳은 www.youtube.com/watch?v=_hxFgg7TLZQ 로 영상을 보고 대강 이해를 하고 코드를 짜기 시작했다.

간단히 설명하자면

DFS => stack으로 탐색 가능. 연결되는 노드를 차례로 스택에 저장

BFS => queue로 탐색 가능. 연결되는 노드를 차례로 큐에 저장

 

자세한 로직은 유튜브를 참고하면 될것이다. 물론 유튜브 과정 그대로 코딩을 하려니 코드가 길고 더러워졌다. 역시 머리를 써서 깔끔하게 정리하고 코딩에 들어가야한다.

더러운 DFS, BFS코드

import time

n,m,start = map(int, input().split())
line = []
for i in range(m):
    line.append(tuple(map(int, input().split())))

dfs = [start]
bfs = [start]
output = []
while(len(dfs)!=0):
    target = dfs.pop()
    # 연결된 거 확인
    con = []
    for item in line:
        if target in item:
            if item[0] == target:
                con.append(item[1])
            else:
                con.append(item[0])
    con = list(set(con))
    con.sort(reverse=True)
    for i in con:
        if (i in output):
            continue
        dfs.append(i)
    if (target not in output):
        output.append(target)
    if len(output) == n:
        break
for i in output:
    print(i, end=" ")
print()

#bfs
output = []
while(len(bfs)!=0):
    target = bfs[0]
    del bfs[0]
    # 연결된 거 확인
    con = []
    for item in line:
        if target in item:
            if item[0] == target:
                con.append(item[1])
            else:
                con.append(item[0])
    con = list(set(con))
    con.sort()
    for i in con:
        if (i in bfs) or (i in output):
            continue
        bfs.append(i)
    if target not in output:
        output.append(target)
for i in output:
    print(i, end=" ")
print()

 

정리한 DFS,BFS코드

from collections import deque

n,m,start = map(int, input().split())
graph = {}
for i in range(m):
    a,b = map(int, input().split())
    if a not in graph:
        graph[a] = [b]
    else:
        graph[a].append(b)
    if b not in graph:
        graph[b] = [a]
    else:
        graph[b].append(a)
dfs = [start]
output = []
while dfs:
    target = dfs.pop()
    if target not in output:
        output.append(target)
        if target in graph:
            tmp = list(set(graph[target]) - set(output))
            tmp.sort(reverse=True)
            dfs += tmp
for i in output:
    print(i, end=" ")
print()

#bfs
bfs = deque([start])
output = []
while bfs:
    target = bfs.popleft()
    if target not in output:
        output.append(target)
        if target in graph:
            tmp = list(set(graph[target]) - set(output))
            tmp.sort()
            bfs += tmp
for i in output:
    print(i, end=" ")
print()

코드를 그나마 정리를 하면 위와 같다.

이때 중요한 것은 반드시 정렬을 해주고 stack이나 queue에 넣어주어야 한다. set하면 그냥 정렬 잘 되서 들어갈 줄 알았는데 고런걸로 통과가 안되기도 하는 것을 알게 되었다.

set해도 sort로 정렬을 시켜주자