BFS, DFS

BFS

1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김
2. 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입
4. 큐가 빌 때까지 2번을 반복

• 모든 칸이 큐에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 $O(N)$

CPP Pseudocode

queue<pair<int, int>> qu;    // 탐색용 queue 생성
dist[0][0] = 1;    // 방문 기록
qu.push({ 0, 0 });    // 해당 칸을 큐에 삽입
​
	while (!qu.empty()) {
		pair<int, int> cur = qu.front();
		qu.pop();                        // 큐에서 원소를 꺼냄
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];    // 인접 칸의 X 좌표 계산
			int ny = cur.Y + dy[dir];    // 인접 칸의 Y 좌표 계산
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) { continue; }    // 바운드 처리
			if (dist[nx][ny] != 0 || board[nx][ny] == 0) { continue; }    // 방문 여부, 방문 가능 여부 처리
			dist[nx][ny] = dist[cur.X][cur.Y] + 1;        // 방문 기록
			qu.push({ nx, ny });        // 해당 칸을 큐에 삽입
		}
	}

DFS

1. 시작하는 칸을 스택에 넣고 방문했다는 표시를 남김
2. 스택에서 원소를 꺼내어 그 칸과 상하좌우로 인접한 칸에 대해 `3번을 진행
3. 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입
4. 스택이 빌 때까지 2번을 반복

• 모든 칸이 스택에 1번씩 들어가므로 시간복잡도는 칸이 N개일 때 $O(N)$

방문한 곳을 다시 방문할 수 있는 경우

BFS의 경우 MLE, DFS의 경우 TLE가 뜰 수 있다.
이럴 땐 메모이제이션(DP)를 사용해야 한다.
[2186] 문자판을 확인하라.