모각코 4회차

목표 : 이것이 코딩테스트다 with PYTHON DFS/BFS 관련 공부를 하고 문제를 풀어보자.

DFS와 BFS를 알아보기 전에 스택과 큐와 같은 자료구조를 먼저 짚어보았다.

스택(Stack)은 쉽게 말해 후입선출(First in Last Out)으로 나중에 입력받은 것이 먼저 나오는 자료구조를 뜻한다. 파이썬에서는 리스트의 append와 pop 메소드를 활용하여 나타낸다.

큐(queue)는 선입선출(First in First Out)으로 먼저 입력받은 것이 먼저 나오는 자료구조이다. 파이썬에서는 collections 모듈에서 제공하는 deque 자료구조를 활용한다.

DFS(Depth - First Search)

깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS(Breadth First Search)

너비 우선 탐색이라고 부르며 가까운 노드부터 탐색하는 알고리즘이다.

동작방식

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

이를 활용하여 문제를 풀어보자.

문제 해결 방법

위 문제는 0으로 이루어진 공간의 개수를 출력하는 문제이다. DFS를 이용하여 0이 있는 공간을 상하좌우 모두 체크하고 공간이 없으면 개수를 1씩 늘려가며 결과값을 출력하도록 한다.
여기서 N과 M의 범위가 초과하지 않도록 주의해야한다.

문제 해결 방법

(1,1)을 기준으로 BFS를 수행하여 모든 노드의 값을 거리 정보로 넣으면 된다.
각 정점마다 상하좌우 좌표를 확인하여 그 값을 더해서 저장한다.

이상이다.