[백준 BOJ] 1260번(DFS와 BFS) Python 풀이

# 해당 포스팅은 이제 막 알고리즘 공부를 시작한 초보 수준에서 작성했음을 이해해주시고, 비난보다는 따뜻한 조언을 부탁드립니다.

---

안녕하십니까, 간토끼입니다.

오늘은 백준 1260번 (DFS와 BFS)에 대해 다뤄보겠습니다.

 

1. 문제 링크

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

1260번: DFS와 BFS

일반적인 DFS, BFS 문제입니다.

이코테(이것이 코딩테스트다) 책을 공부하면서 마침 어제 DFS, BFS 알고리즘을 배웠는데요.

그래프 탐색이라는 게 생각보다 헷갈리더라고요. 아직 개념이 와닿지는 않지만, 직접 문제를 풀어봐야 개념이 와닿을 것 같아서 풀었습니다.

입력으로는 첫 줄에 노드, 간선, 시작 지점이 주어지고, 둘째 줄부터 각 노드의 연결 관계가 주어집니다.

출력으로는 DFS, BFS 함수를 통해 탐색한 노드의 순서별로 출력해주면 됩니다.

 

2. 접근 방법

다음과 같이 접근하였습니다.

DFS, BFS 함수를 구현하는 건 이코테 책에서도 나와있는 내용이니까 방법 자체는 생략하고요.

먼저 둘째줄부터 들어오는 입력(노드의 연결 관계)을 인접 리스트로 바꿔줘야 합니다.

간단하게 append 함수를 이용하면 쉽게 바꿔줄 수 있는데요.

이때 입력 조건을 보면 '방문 가능한 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문'이라고 적혀있습니다.

따라서 입력을 받을 때마다 sorting을 해줬습니다.

예를 들어 [5, 4], [5, 2] 입력이 주어진다고 가정하면, 5번 노드는 4번과 2번 노드와 연결 관계가 있다고 할 수 있는데요.

이때 인접 리스트로 바꿔주기 위해 graph[5].append(4), graph[5].append(2)를 해주게 되면

graph[5] => [4, 2] 가 되고, 이는 탐색시 2번 노드와 4번 노드 중 4번 노드를 먼저 방문하게 되므로 문제의 조건에 위배됩니다.

이를 위해 입력 받을 때마다 sort를 해주면 입력이 종료됐을 때 각 i번째의 리스트 graph[i]의 경우 작은 노드부터 정렬돼있으니 문제 없음을 알 수 있습니다.

그리고 방문한 노드를 순서대로 출력하기 위해 dfs_visited, bfs_visited 라는 별도의 리스트를 추가해주었습니다.

 

3. 코드

# 백준 1260 : DFS와 BFS

# 초기 세팅
N, link, V = map(int, input().split())
graph = [ []*(N+1) for _ in range(N+1)]

# 인접 리스트 만들기
for i in range(link):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()
    
# 방문 여부 체크
visited_1 = [False]*(N+1) # dfs용
visited_2 = [False]*(N+1) # bfs용

# 1. DFS 만들기
dfs_visited = []
def dfs(graph, v, visited):
    if visited[v] == False:
        visited[v] = True
        
    global dfs_visited
    dfs_visited.append(v)
    
    # 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
            

# 2. BFS 만들기
bfs_visited = []
from collections import deque

def bfs(graph, v, visited):
    queue = deque([v]) # start에 대한 큐
    
    if visited[v] == False:
        visited[v] = True
        
    global bfs_visited
    while queue:
        # 큐에서 하나씩 원소를 뽑아 출력
        i = queue.popleft()
        bfs_visited.append(i) # 방문한 노드 저장
        # 해당 원소(i)와 연결된 아직 방문하지 않은 원소들을 큐에 삽입
        for j in graph[i]:
            if not visited[j]:
                queue.append(j)
                visited[j] = True
            
            
dfs(graph, V, visited_1)
bfs(graph, V, visited_2)
print(*dfs_visited, sep = ' ')
print(*bfs_visited, sep = ' ')

 

감사합니다.

잘 읽으셨다면 게시글 하단에 ♡(좋아요) 눌러주시면 감사하겠습니다 :)

(구독이면 더욱 좋습니다 ^_^)

* 본 블로그는 학부생이 운영하는 블로그입니다.

따라서 포스팅에 학문적 오류가 있을 수 있으며, 이를 감안해서 봐주시면 감사하겠습니다.

 

---

- 간토끼(DataLabbit)

- B.A. in Economics, Data Science at University of Seoul