[백준][bfs] 14497 주난의 난 (두개의 큐를 이용한 bfs) c++ 추가 구현

목차

 

참고: dfs와 bfs를 혼용한 방식 

https://be-senior-developer.tistory.com/121

[백준][bfs] 14497 주난의 난 c++ 구현

 

이번에는 두 개의 큐를 이용한 방식을 통해 풀어보고자 한다.

또한 가져가면 좋을 아이디어를 설명하고자 한다.

 

수 하나로 이차원 좌표 표현하기 

// 범위가 300이라고 300을 곱하면 안된다
int num = startX * 1000 + startY;
q.push(num);
    


//이런식으로 좌표를 수 하나로 표현 가능하다

int x = q.front() / 1000;
int y = q.front() % 1000;

 

 

두개의 큐를 이용한 코드 구현

void bfs() {
	queue<int> q;
	int num = startX * 1000 + startY;
	q.push(num);
	visit[startY][startX] = 1;
	while (board[endY][endX] != '0') {
		queue<int> temp;
		cnt++;
		while (!q.empty()) {
			int x = q.front() / 1000;
			int y = q.front() % 1000;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx <0 || nx > M - 1 || ny < 0 || ny > N - 1 || visit[ny][nx])
					continue;
                //0이 아니면 다른 큐에 저장해 놓는다 -> 다음 탐색을 할 bfs이므로
				if ( board[ny][nx] != '0') {
					temp.push(nx * 1000 + ny);
					board[ny][nx] = '0';
					visit[ny][nx] = 1;
				}
                //0이면 지금 bfs로 탐색한다
				else {
					q.push(nx * 1000 + ny);
					visit[ny][nx] = 1;
				}
			}
		}
		q = temp;  // 첫 bfs가 끝났으므로 다음 탐색할 bfs를 넣어준다
	}

}

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;


int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };
int N, M, startX, startY, endX, endY;
char board[300][300] = { 0 };
int visit[300][300] = { 0 };
int cnt = 0;



//두개의 큐를 이용한 bfs

void bfs() {
	queue<int> q;
	int num = startX * 1000 + startY;
	q.push(num);
	visit[startY][startX] = 1;
	while (board[endY][endX] != '0') {
		queue<int> temp;
		cnt++;
		while (!q.empty()) {
			int x = q.front() / 1000;
			int y = q.front() % 1000;
			q.pop();
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx <0 || nx > M - 1 || ny < 0 || ny > N - 1 || visit[ny][nx])
					continue;
				if ( board[ny][nx] != '0') {
					temp.push(nx * 1000 + ny);
					board[ny][nx] = '0';
					visit[ny][nx] = 1;
				}
				else {
					q.push(nx * 1000 + ny);
					visit[ny][nx] = 1;
				}
			}
		}
		q = temp;
	}

}


int main() {
	char symbol;
	cin >> N >> M;
	cin >> startY >> startX >> endY >> endX;
	startY--, startX--, endY--, endX--;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> symbol;
			board[i][j] = symbol;
		}
	}
	bfs();

	cout <<cnt;
}

 

유사한 문제

치즈

https://www.acmicpc.net/problem/2636