BFS,DFS

1. 그래프 탐색 : 어떤것들이 연속해서 이어질때, 모두 확인하는 방법.

• Vertex(노드,어떤것) + Edge(간선,이어지는것)

1-1. 그래프 탐색 종류

• BFS : Breadth First Search. (너비우선)

• DFS : Depth First Search. (깊이우선)
  

1-2. How to implement BFS as a code.

1. Start point에 연결된 Vertex 찾기.
2. Found Vertex 를 Queue에 저장
3. Queue의 가장 먼저 것을 뽑아서 반복

1-3. 자료구조를 어떻게 사용할 것인가.

1. 검색할 그래프에 대한 자료구조.
2. 방문여부를 확인하기위한 자료구조 (재방문 금지)
3. Queue : BFS를 실행하기위한 조건

1-4. 연습문제 백준 1926번

• 1이 나왔을때 주변에 1이 있으면 찾아나가고 0이면 찾지않기 = BFS
• for문 돌면서 BFS를 돌린다.
• 이중 for문으로 BFS call value = 1 and visited = False 여야 BFS 실행
• BFS 돌면서 그림 개수 +1, 최댓값을 갱신

사용하는 자료구조 :

• 그래프 전체 지도 : 2차원 0,1 배열 =int[ ][ ]
• 방문여부 : bool[ ][ ]
• Queue(BFS) or deque

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
array = [list(map(int, input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
#   기본 자료구조 세팅

direction_y = [0, 1, 0, -1]
direction_x = [1, 0, -1, 0]


def bfs(y, x):
    result = 1
    queue = deque([(y, x)])
    while queue:
        now_y, now_x = queue.popleft()
        for k in range(4):
            next_y = now_y + direction_y[k]
            next_x = now_x + direction_x[k]
            if 0 <= next_y < n and 0 <= next_x < m:
                if array[next_y][next_x] == 1 and visited[next_y][next_x] == False:
                    result += 1
                    visited[next_y][next_x] = True
                    queue.append((next_y, next_x))
    return result


count = 0
max_v = 0
for j in range(n):
    for i in range(m):
        if array[j][i] == 1 and visited[j][i] == False:
            visited[j][i] = True
            count += 1
            max_v = max(max_v, bfs(j, i))
print(count)
print(max_v)

2. DFS

2-2. How to implement DFS as a code.

1. Start point에 연결된 Vertex 찾기.
2. 연결된 Vertex를 끝날때 까지 계속해서 찾음
3. Recursion 사용 or 비재귀는 Stack을 이용하여 구현

2-3. 자료구조를 어떻게 사용할 것인가.

1. 검색할 그래프에 대한 자료구조.
2. 방문여부를 확인하기위한 자료구조 (재방문 금지)

2-4. 연습문제 백준 2667.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
array = [list(map(int, input().strip())) for _ in range(n)]
visited = [[False] * n for _ in range(n)]
result = []
separate = 0
direction_x = [1,0,-1,0]
direction_y = [0,1,0,-1]


def dfs(x, y):
    global separate
    separate += 1
    for k in range(4):
        next_y = y + direction_y[k]
        next_x = x + direction_x[k]
        if 0 <= next_x < n and 0 <= next_y < n:
            if array[next_x][next_y] == 1 and visited[next_x][next_y] == False:
                visited[next_x][next_y] = True
                dfs(next_x, next_y)


for i in range(n):
    for j in range(n):
        if array[i][j] == 1 and visited[i][j] == False:
            visited[i][j] = True
            separate = 0
            dfs(i,j)
            result.append(separate)

result.sort()
print(len(result))
for e in result:
    print(e)