- dfs : 최대한 깊게 방문하지 않은 노드들에 쭉 방문하다가, 더이상 진행할 수 있는 인접정점이 없으면 되돌아감 - 재귀
- bfs : 한 노드에서 인접노드까지 방문한 적이 없는 모든 노드를 queue에 삽입. que는 FIFO 방식이라서 순차적인 구현
DFS
from collections import deque
r,c = map(int, input().split())
pasture = [list(input()) for _ in range(r)]
visit = [[0]*c for _ in range(r)]
d = [(0,1),(0,-1),(1,0),(-1,0)]
cnt = 0
def dfs(x, y) :
visit[x][y] = 1
for dx, dy in d :
nx,ny = x+dx, y+dy
if 0 <= nx < r and 0<= ny < c :
if not visit[nx][ny] and pasture[nx][ny] == '#' :
dfs(nx, ny)
for x in range(r) :
for y in range(c) :
# 그래프를 순회하면서 #(clump) 찾기 -> 찾으면 dfs 실행
if not visit[x][y] and pasture[x][y] == '#' :
dfs(x, y)
cnt += 1
print(cnt)
- 방문 표시를 위해서 입력 받는 그래프의 크기와 똑같은 visit 배열
- 상하좌우 탐색을 위한 direction 001-1선언
- dfs를 실행하면 방문 표시를 위한 visit에 1로 표시
- 탐색을 시작한 좌표에 direction을 활용해서 주변 방문
- 지금까지 방문한 적이 없고, 방문한 곳이 # 이라면 dfs 실행.. dfs 실행할 때마다 count..
BFS
from collections import deque
r,c = map(int, input().split())
pasture = [list(input()) for _ in range(r)]
# 상하좌우
d = [(-1,0), (1,0), (0,-1), (0,1)]
cnt = 0
def bfs(y, x) :
# 방문한 적이 없는 노드는 que에 삽입하는ㄱ ㅔ bfs
# q에 모든 노드 위치를 다 넣고, 방문 표시를 해줌
q = deque()
q.append((y,x))
pasture[y][x] = '1'
# q를 돌면서 방문한 노드를 체크해줌..
while q :
y,x = q.popleft()
# 상하좌우 돌기
for dy, dx in d :
Y,X = y+dy, x+dx
if 0 <= Y < r and 0 <= X < c and pasture[Y][X] == '#' :
q.append((Y,X))
pasture[Y][X] = '1'
for x in range(r) :
for y in range(c) :
# 그래프를 순회하면서 #(clump) 찾기 -> 찾으면 dfs 실행
if pasture[x][y] == '#' :
bfs(x, y)
cnt += 1
print(cnt)
- bfs 함수 앞쪽에는 방향, 그래프, 입력, q 정도 선언
- q.append(x,y)와 방문 표시로 시작
- q를 돌면서 x,y 좌표에는 q에 있는 좌표 (popleft)
- 선언한 방향을 활용해서 nx, ny 좌표 설정
- nx, ny 범위 조건 체크
- 원하는 조건 확인 & 방문 표시 & q에 방문한 nx, ny 좌표 삽입
그래프 문제 풀때
- 2차원 리스트 입력 받기 [list(input().split()) for _ in range(n)]
- direction 0, 0, 1, -1
- 조정한 nx ny는 r, c 범위 확인
