[Coding Test] 5주차 - DFS와 BFS

주제

DFS와 BFS

1. DFS와 BFS?

대표적인 그래프 탐색 알고리즘으로 DFS(Deep First Search), BFS(Breadth First Search) 두 종류가 있다. 그래프 순회 문제는 주로 그래프의 한 정점에서 시작해 남은 모든 정점을 방문하는 문제

+ 그래프란? 

연결되어있는 원소간의 관계를 표현한 자료구조 중 하나로 정점(노드)과 간선의 집합이다.

• 정점(Vertex) : 노드라고도 하며 데이터를 저장
• 간선(Edge) : 정점을 연결하는 선 (link, branch 모두 같은 말)
• 인접 정점(adjacent Vertex) : 간선에 의해 직접 연결된 정점 
• 단순 경로(simple path) : 경로에서 같은 간선을 두번 지나가지 않는 경로 
• 차수(degree) : [무방향 그래프] 하나의 정점에 인접한 정점의 수 
• 진출 차수(in-degree) : [방향 그래프] 외부로 향하는 간선의 수
• 진입 차수(out-degree) : [방향 그래프] 외부에서 들어오는 간선의 수
• 경로 길이(path length) : 경로를 구성하는데 사용된 간선의 수
• 사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우

2. DFS : 깊이 우선 탐색

시작 노드에서 시작해서 다음 분기 branch로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

예: 미로 길찾기를 할 때 한 방향으로 쭉 가다가 막히면 가까운 갈림길로 돌아와서 다른 방향으로 재탐색하는 길찾기

특징

• 자기 자신을 호출하는 재귀적 형태
• 어떤 노드를 방문했는지 visit여부를 반드시 검사해야한다
• DFS가 BFS보다 구현이 간단하나 탐색 속도는 조금 느리다.
• 얻은 답이 최단경로라는 보장이 없다
• 구현시 재귀함수나 스택으로 구현

출처 wikipedia

수도코드 구현

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

재귀적 호출

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)

스택 사용

---

3. BFS 넓이 우선 탐색

한 노드를 시작으로 가장 가까운 노드부터 탐색하는 방법. 큐라는 자료구조를 사용한다.

예 : 목적지까지 최단 경로 구하기

특징

• 큐라는 자료구조 사용 (FIFO)
• DFS에 비해 구현은 어려우나 탐색 시간은 더 짧다
• 두 노드 사이의 최단 경로를 찾고 싶을 때 사용

출처 wikipedia

procedure BFS(G, root) is
      let Q be a queue
      label root as explored
      Q.enqueue(root)
      while Q is not empty do
          v := Q.dequeue()
          if v is the goal then
              return v
          for all edges from v to w in G.adjacentEdges(v) do
              if w is not labeled as explored then
                  label w as explored
                  w.parent := v
                  Q.enqueue(w)

4. DFS와 BFS 선택

모든 노드를 검색할 때는 시간 복잡도는 동일하나 문제 유형에 따라 더 적합한 유형이 있다.

• DFS, BFS 둘 다 상관 없음
  • 그래프의 모든 노드를 방문하는 경우
• DFS를 사용
  • 경로의 특징을 저장해야 하는 경우
  • 검색 대상 그래프가 정~말 클 때
• BFS를 사용
  • 최단 거리를 구하는 경우

---

문제

2606 바이러스

문제 : 1번 컴퓨터가 바이러스에 걸렸을 때 그 컴퓨터와 연결되어있는 컴퓨터들은 모두 바이러스에 걸리게 된다. 이 때 바이러스가 걸린 컴퓨터의 수를 구하시오

풀이

기본적인 깊이관련 문제로 DFS, BFS 모두 풀이가 가능한 문제이다. 두가지 경우로 모두 풀어보았는데, DFS는 전부 탐색해야 할때, 위치에 조건이 있을 때 주로 사용하고, BFS는 최단 경로를 사용할 때 주로 사용한다!

코드

from collections import deque

n = int(input())
pair = int(input())

# 그래프 만들기
graph ={}
for i in range(n):
    graph[i+1] = set()
for i in range(pair):
    a,b = map(int,input().split())
    graph[a].add(b)
    graph[b].add(a)

visited = [0] * (n+1) # 방문 리스트 초기화

# 넓이 우선 탐색 함수
def bfs(start):
    to_visit = deque([start])
    cnt = 0
    visited[start] = 1
    while to_visit:
        node = to_visit.popleft()
        for i in graph[node]:
            if not visited[i]:
                cnt +=1
                visited[i] = 1
                to_visit.append(i)
    return cnt

#깊이 우선 탐색 함수
def dfs(start):
    to_visit = [start]
    visited[start] = 1
    cnt = 0
    while to_visit:
        node = to_visit.pop()
        for i in graph[node]:
            if not visited[i]:
                visited[i] = True
                to_visit.append(i)
                cnt +=1
    return cnt

print(dfs(1))

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

2606번: 바이러스

---

2667 단지 번호 붙이기

문제

지도가 주어졌을 때 ( 1은 집, 0은 빈 곳) 붙어있는 마을을 단지로 정의하고, 단지의 수와 단지의 집의 수를 출력하기

풀이

bfs와 dfs로 모두 풀이할 수 있는 문제인데 bfs로 풀었다!움직일 수있는 x,y의 범위를 정하여 현 위치에서 4가지 방향으로 움직일 때 생길 수 있는 경우에 맞춰 탐색을 진행한다! 시작점이 주어지지 않았으므로 모든 경우에 대해 진행하게 되는데, 이 때 한 번 방문한 곳은 방문하지 않아야하기때문에 방문한 곳을 모두 0으로 바꿔버렸다.

from collections import deque
n = int(input())

graph = [list(map(int,input().rstrip())) for _ in range(n)] # 지도
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs1(x1,y1):
    #1인 경우에만 확인하기

    to_visit = deque()
    to_visit.append((x1,y1))
    # visited[x][y] = 1 visit로 두번 관리하지 않고 1인 자리를 0으로 바꿔버려서 1일 떄만 검색할 수 있도록 만듦
    graph[x1][y1] = 0
    cnt =1
    while to_visit:
        x,y = to_visit.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx>=0 and nx<n and ny>= 0 and ny<n :
                if graph[nx][ny] ==1:
                    graph[nx][ny] = 0  # 0으로 바꿔서 더 못오게
                    to_visit.append((nx,ny))
                    cnt +=1
    return cnt 

# 모든 경우를 다 돌아서 count를 세기
cnt =[]
for i in range(n):
    for j in range(n):
        if graph[i][j] ==1:
            cnt.append(bfs1(i,j))


cnt.sort() # 첫째줄에는 집 종류
print(len(cnt))
for i in range(len(cnt)): # 마을별 집 개수
    print(cnt[i])

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

2667번: 단지번호붙이기

---

7576 토마토

문제

상자안에 토마토가 있다. 익은 토마토가 있을 경우에 다음날 주위의 4방향으로 다른 토마토가 익게 된다. 이 때 상자 안의 토마토가 익기까지 걸리는 최소 시간을 구하시오.

풀이

이 경우 동시에 탐색을 돌려야 하는지.. 고민을 했었는데, 최소범위를 구하기 때문에 동시에 할 필요는 없고 익은 토마토가 있는 경우에 모두 탐색을 돌려보면 된다! 최단 시간을 구하기 위해 bfs로 구현하였다. 익은 토마토에 대해 bfs를 진행 한 후 한번 박스 안의 토마토를 다시 확인해보아 모두 익었으면 최소 시간을, 다 익지 않았으면 -1을 출력한다.

코드

from collections import deque
import sys
m, n = map(int,input().split())
# box = []
# for i in range(n):
#     box.append(list(map(int,input().split())))

box = [list(map(int,sys.stdin.readline().rstrip().split())) for _ in range(n)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def bfs(rot):
    to_visit = rot
    while to_visit:
        x,y = to_visit.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and box[nx][ny] == 0:
                box[nx][ny] = box[x][y] +1  # 일수 계산
                to_visit.append([nx,ny])
                

rot =deque([])
#익은 토마토 rot에 저장하기
for i in range(n):
    for j in range(m):
        if box[i][j] ==1:
            rot.append([i,j])
# 익은 토마토들로 bfs 하여 일수 계산하기
bfs(rot)

m_ans = 0
for line in box:
    for tomato in line:
        if tomato == 0:
            #모두 익지 않는 경우
            print(-1)
            exit()
    m_ans = max(m_ans, max(line))
print(m_ans-1)

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

7576번: 토마토

---

14502 연구소

문제

바이러스의 확산을 최소화하기위해 연구소에 벽을 세워야 한다. 이 때 확보할 수 있는 안전 영역의 최대 크기를 구하기

풀이

1. 벽을 선택한다.
2. 바이러스를 퍼트린다.
3. 바이러스가 퍼지지 않은 안전지역 면적을 구한다.

1~3번의 과정을 벽을 선택하는 모든 경우의 수에 대해서 반복하고, 

마지막에 안전지역의 max값을 반환한다.

코드

from collections import deque
import copy
import sys

def bfs():
    queue = deque()
    tmp_graph = copy.deepcopy(graph)
    for i in range(n):
        for j in range(m):
            if tmp_graph[i][j] == 2:
                queue.append((i, j))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if tmp_graph[nx][ny] == 0:
                tmp_graph[nx][ny] = 2
                queue.append((nx, ny))

    global answer
    cnt = 0

    for i in range(n):
        cnt += tmp_graph[i].count(0)

    answer = max(answer, cnt)


def makeWall(cnt):
    if cnt == 3:
        bfs()
        return

    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                graph[i][j] = 1
                makeWall(cnt+1)
                graph[i][j] = 0

n, m = map(int, input().split())
graph = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

for i in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))

answer = 0
makeWall(0)
print(answer)