DFS BFS 모음 (BOJ 1260, 11725, 2667)

DFS와 BFS는 이진탐색보다 유독 문제에서 마주쳤을 때 당황스러웠다. DFS나 BFS로 풀 수 있는 문제를 모아서 리뷰해봤다. 

1. DFS와 BFS

DFS와 BFS 복습을 위한 문제^^*

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

1260번: DFS와 BFS

코드

from collections import deque
N, E, start = map(int, input().split())
arr = []
graph = [[] for _ in range(N+1)]
 
for i in range(E):
    arr.append(list(map(int, input().split())))
    idx1 = arr[i][0]
    idx2 = arr[i][1]
    graph[idx1].append(idx2)
    graph[idx2].append(idx1)
 
for i in range(len(graph)):
    graph[i].sort()
 
visit = [False]*(N+1)
visited = [False]*(N+1)
def dfs(graph,v,visit):
    visit[v] = True
    print(v, end=' ')
    for i in graph[v]:
        if not visit[i]:
            dfs(graph, i, visit)
 
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
 
 
dfs(graph, start, visit)
print()
bfs(graph, start, visited)

 

1. 입력으로 node의 수, edge의 수, 시작 노드를 받는다. 
더블리스트의 그래프로 만들어준다. 

2. DFS는 시작점(start)을 visit=True하고, start 노드와 연결된 노드가 visit=False라면, dfs를 실행한다. (반복)

3. BFS는 시작점(start)을 queue에 넣은 후, visited = True하고, queue에서 popleft()를 하여 나온 노드와 연결된 모든 노드 중 visited=False인 노드들을 queue에 넣는다. 그리고 visited=True로 바꿔준다. 

2. 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

코드

from collections import deque
N = int(input())
arr = []
graph = [[] for _ in range(N+1)]
 
for i in range(N-1):
    arr.append(list(map(int, input().split())))
    idx1 = arr[i][0]
    idx2 = arr[i][1]
    graph[idx1].append(idx2)
    graph[idx2].append(idx1)
 
visited = [False]*(N+1)
 
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True
    parent = 0
    while queue:
        v = queue.popleft()
        parent = v
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = v
 
bfs(graph, 1, visited)
for i in range(2, N+1):
    print(visited[i])

1. 입력으로 노드의 수 (N), 엣지(N-1)를 받는다. 
더블리스트의 그래프로 만들어주고, DFS와 달리 정렬할 필요없다. 

2. 코드는 BFS로 풀었는데, visited를 True, False 대신 부모 노드의 ID로 기록한다. 

3. 단지번호붙이기

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

2667번: 단지번호붙이기

코드

n = int(input())
graph = []
for i in range(n):
    graph.append(list(map(int, input())))
 
visited = [[False for _ in range(n)] for _ in range(n)]
count = 1
 
#이동할 네 방향
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
 
def dfs(x,y):
    global count
    for i in range(4): #각 지점의 북,동,남,서(시계방향) 살핌.
        nx = x+dx[i]
        ny = y+dy[i]
        if 0<=nx<n and 0<=ny<n:
            # 그래프에서 1인데 아직 방문 안한 곳
            if visited[nx][ny]==False and graph[nx][ny]==1:
                visited[nx][ny] = True
                count+=1
                dfs(nx, ny)
 
total = 0
result = []
for i in range(n):
    for j in range(n):
        if visited[i][j] == False and graph[i][j]==1:
            visited[i][j] = True
            total += 1
            dfs(i, j) #단지 순회해서 count했음.
            result.append(count)
            count = 1 #count 다시 초기화해줌.
 
result.sort()
print(total)
for i in result:
    print(i)