[Algorithm] 7주차 스터디 - DFS, BFS(백준 1260, 2606, 1012, 14502)

문제 (1260: DFS와 BFS)

www.acmicpc.net/problem/1260

풀이

BFS와 DFS의 차이점을 기억하면서 풀자

DFS(Depth-First-Search) : 깊이 우선 탐색은 맹목적 탐색방법의 하나로 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.

참고하면 좋을 사이트 : swexpertacademy.com/main/visualcode/main.do#/home/editor/R/57c78219a4c12ab823c2fbd2

BFS(Breadth-First-Search) : 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.

참고하면 좋을 사이트: swexpertacademy.com/main/visualcode/main.do#/home/editor//

소스코드

from sys import stdin
n, m, v = map(int, stdin.readline().split())
matrix = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    line = list(map(int, stdin.readline().split()))
    matrix[line[0]][line[1]] = 1
    matrix[line[1]][line[0]] = 1

def bfs(start):
    visited = [start]
    queue = [start]
    while queue:
        n = queue.pop(0)
        for c in range(len(matrix[start])):
            if matrix[n][c] == 1 and (c not in visited):
                visited.append(c)
                queue.append(c)
    return visited

def dfs(start, visited):
    visited += [start]
    for c in range(len(matrix[start])):
        if matrix[start][c] == 1 and (c not in visited):
            dfs(c, visited)
    return visited

print(*dfs(v,[]))
print(*bfs(v))

 

문제 (2606 : 바이러스)

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

풀이

입력 받은 데이터를 인접리스트로 만들고 컴퓨터 1번부터 DFS를 동작한다.

소스코드

from sys import stdin
read = stdin.readline
dic={}
for i in range(int(read())):
    dic[i+1] = set()
for j in range(int(read())):
    a, b = map(int,read().split())
    dic[a].add(b)
    dic[b].add(a)

def dfs(start, dic):
    for i in dic[start]:
        if i not in visited:
            visited.append(i)
            dfs(i, dic)
visited = []
dfs(1, dic)
print(len(visited)-1)

문제 (1012: 유기농 배추)

www.acmicpc.net/problem/1012

풀이

방문한 영역을 제외하고 DFS를 동작한다.

소스코드

import sys
sys.setrecursionlimit(10000)

def dfs(X, Y):
    global MAP, M, N
    // 상 하 좌 우로 이동하며 탐색할 준비
    dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
    MAP[X][Y] = -1
    for i in range(4):
        XX, YY = X + dx[i], Y + dy[i]
        // 배열의 인덱스를 넘지 않도록
        if XX < 0 or XX == M or YY < 0 or YY == N:
            continue
        // 배추가 있으면 
        if MAP[XX][YY] == 1:
            MAP[XX][YY] = -1
            dfs(XX, YY)

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())
    MAP = [[0]*N for _ in range(M)]
    count = 0
    for _ in range(K):   
        X, Y = map(int, input().split())
        MAP[X][Y] = 1
    for i in range(M):
        for j in range(N):
            if MAP[i][j] > 0:
                dfs(i, j)
                count += 1
    print(count)

문제 (14502: 연구소)

www.acmicpc.net/problem/14502

풀이

각 구역마다 벽 3개를 세워서 바이러스를 퍼뜨린 후 바이러스 개수의 최솟값을 찾는다.
그 때의 바이러스의 최솟값과 벽의 개수를 저장한 후
연구소 전체 크기에서 바이러스의 최솟값과 벽의 개수를 빼면 안전 영역의 최댓값이 나온다.

소스코드

import copy
# 벽 세워보기
def wall(idx, x, y):
    global minV
    if(idx == 3):
        temp = copy.deepcopy(check)
        qs = copy.deepcopy(q)
        a = virus(temp, qs)
        if(a < minV):
            minV = a
        return
    else:
        # 이 부분 처리를 해주지 않으면 시간초과
        ## if문을 통해 이전 재귀에서 탐색한 범위를 제외하고 for문을 수행하도록
        for i in range(x, n):
            if(i == x):
                k = y
            else:
                k = 0
            for j in range(k, m):
                if(arr[i][j] == 0 and check[i][j] == 0):
                    check[i][j] = 1
                    wall(idx+1, i, j+1)
                    check[i][j] = 0

# 바이러스 퍼뜨리기
def virus(temp, qs):
    global minV
    res = len(qs)
    while(qs):
        if(res > minV):
            return minV
        x, y = qs.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if(0<=nx<n and 0<=ny<m):
                if(temp[nx][ny] == 0):
                    temp[nx][ny] = 2
                    qs.append((nx,ny))
                    res += 1
    return res

dx = [0,1,0,-1]
dy = [1,0,-1,-0]
n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
check = copy.deepcopy(arr)
q = []
minV = 99999
cnt = 0
# 벽의 개수와 바이러스의 위치 저장
for i in range(n):
    for j in range(m):
        if(arr[i][j] == 1):
            cnt += 1
        elif(arr[i][j] == 2):
            q.append((i,j))
wall(0,0,0)
# 안전영역의 크기는 전체크기 - 바이러스의 최소값 - 벽의개수
print(m*n - minV - cnt -3)

 

참고 사이트

swexpertacademy.com/main/main.do
https://hidelookit.tistory.com/31