[백준/6186] Best Grass | bfs, dfs

• 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 범위 확인