[알고리즘] BFS & DFS

1260번- bfs&dfs

• 기본적인 dfs & bfs
• bfs의 경우 큐 자료구조 이용
• dfs의 경우 스택 자료구조 이용(재귀)
• 정점 방문을 위한 visited 리스트 생성

visited = [False for _ in range(N)]

전체 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def dfs(G,visited,vertex):
    """
    dfs는 스택 자료구조(재귀) 이용
    """
    visited[vertex] = True
    print(vertex+1, end = " ")
    for p in G[vertex]:
        if not visited[p]:
            dfs(G,visited,p)
 
def bfs(G,visited,vertex):
    """
    bfs는 큐 자료구조 이용
    """
    Q = deque()
    Q.append(vertex)
    visited[vertex] = True
    while Q:
        current  = Q.popleft()
        print(current+1,end = " ")
        for p in G[current]:
            if not visited[p]:
                Q.append(p)
                visited[p] = True
 
N, M, V = map(int,input().split())
G = [[]for _ in range(N)]
# 인접 리스트 생성
for _ in range(M):
    s,e = map(int,input().split())
    G[s-1].append(e-1)
    G[e-1].append(s-1)
for row in G:
    row.sort()
visited = [False for _ in range(N)]
dfs(G,visited,V-1)
print()
visited = [False for _ in range(N)]
bfs(G,visited,V-1) 

2606번 - 바이러스

• 1번 컴퓨터로부터 바이러스 생성
• 해당 컴퓨터와 인접한 컴퓨터에 대하여 방문하지 않았으면 cnt +1

for next in G[current]:
        if not visited[next]:
            visited[next] = True
            cnt+=1
            Q.append(next)

• 인접 리스트, 인접 행렬 중 인접 리스트 선택
  • 간선이 적을 경우 인접 리스트가 실행속도가 빠름

## 전체 코드
``` python
import sys
from collections import deque
input = sys.stdin.readline
 
N = int(input())
E = int(input())
G = [[] for _ in range(N)]
visited = [False for _ in range(N)]
 
for _ in range(E):
    s,e = map(int,input().split())
    G[s-1].append(e-1)
    G[e-1].append(s-1)
Q = deque()
Q.append(0)
visited[0] = True
cnt = 0
while Q:
    current = Q.popleft()
    for next in G[current]:
        if not visited[next]:
            visited[next] = True
            cnt+=1
            Q.append(next)
print(cnt)

2667번 - 단지번호붙이기

• G 값 ( 0: 집이 없는 곳, 1 : 집이 있는 곳, 2: 방문한 곳)
• G[x][y] 값이 1 이라면 dfs 시작 단지 내 아파트 리스트 추가

  apts = []
  

for i in range(N):
for j in range(N):
if G[i][j]==1:
apts.append(dfs(i,j))

- 방문한 아파트에 경우 2로 할당
``` python
    if 0<=x<N and 0<=y<N and G[x][y] == 1: # 방문하지 않았다면
        G[x][y] = 2 # 방문 표시

• 인근 아파트 (상,하,좌,우)에 대하여 dfs 진행

        cnt+=dfs(x-1,y)
        cnt+=dfs(x,y-1)
        cnt+=dfs(x,y+1)
        cnt+=dfs(x+1,y)
        return cnt

## 전체 코드
 
``` python
import sys
sys.setrecursionlimit(10**6)
 
def dfs(x,y):
    cnt = 1
    if 0<=x<N and 0<=y<N and G[x][y] == 1: # 방문하지 않았다면
        G[x][y] = 2 # 방문 표시
        cnt+=dfs(x-1,y)
        cnt+=dfs(x,y-1)
        cnt+=dfs(x,y+1)
        cnt+=dfs(x+1,y)
        return cnt
    return 0
 
 
N = int(input())
G = []
for _ in range(N):
    G.append(list(map(int,input())))
 
apts = []
 
for i in range(N):
    for j in range(N):
        if G[i][j]==1:
            apts.append(dfs(i,j))
apts.sort() # 단지 내 아파트 수 오름차순 정렬
print(len(apts)) # 단지 수 
for apt in apts:
    print(apt)

7576번 - 토마토

• 인접한 토마토에 대하여 익으므로 bfs을 이용하여 구현
• 맨 처음 익은 토마토를 큐에 추가

for i in range(N):
    for j in range(M):
        if G[i][j] == 1:
            Q.append((i,j))

• 만약 익지 않은 토마토(G = 0)가 있다면 -1 출력
• 익은 토마토들만 있다면 G값중 가장 큰 값-1 출력

# 익지 않은 토마토가 있는 지 , 최대 일 수 확인
for i in range(N):
    for j in range(M):
        if  G[i][j] == 0:
            is_zero = True
        max_days = max(max_days,G[i][j])
if is_zero:
    print(-1)
else:
    print(max_days-1)

전체 코드

import sys
from collections import deque
input = sys.stdin.readline
 
M, N = map(int,input().split())
G = []
for _ in range(N):
    G.append(list(map(int,input().split())))
Q = deque()
# 처음 익은 토마토는 큐에 추가
for i in range(N):
    for j in range(M):
        if G[i][j] == 1:
            Q.append((i,j))
mx_list = [-1,1,0,0]
my_list = [0,0,1,-1]
while Q:
    x,y = Q.popleft()
 
    for mx,my in zip(mx_list,my_list):
        nx = x + mx
        ny = y + my
        if 0<=nx <N and 0<=ny<M and G[nx][ny]== 0  : # 익지 않았다면
            Q.append((nx,ny))
            G[nx][ny] = G[x][y]+1 # days +1
 
max_days = 0
is_zero = False
 
# 익지 않은 토마토가 있는 지 , 최대 일 수 확인
for i in range(N):
    for j in range(M):
        if  G[i][j] == 0:
            is_zero = True
        max_days = max(max_days,G[i][j])
if is_zero:
    print(-1)
else:
    print(max_days-1)