백준/2178/BFS/미로 탐색

백준/2178/BFS/미로 탐색
BFS를 이용한 거리탐색 유형 문제이다.
처음 생각한 풀이법은 분기점을 큐에 넣어놓고 다시 돌아와서 거리를 재는 방법을 생각하고 있다가 그림으로 그려보니 BFS로 방문 표시를 할때 거리도 같이 저장해 놓으면 처음 시작한 위치에서 그 셀까지의 최단 거리를 표시해준다.

int board[100][100];
bool visited[100][100];
int dist[100][100];

위와 같이 거리를 표시해 줄 dist 배열을 선언하였다.

	queue<pair<int, int>> Q;
	Q.push({ 0,0 });	
	visited[0][0] = true;
	dist[0][0] = 1;
	while (!Q.empty()) {
		pair<int, int>cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			//cout << "들어옴" << endl;
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[nx][ny] || board[nx][ny] != 1)continue;
			visited[nx][ny] = true;
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			Q.push({ nx,ny });
		}
	}
...

BFS 방식을 그대로 구현한다음 방문표시를 할때 거리도 같이 표시해주면 된다.

	queue<pair<int, int>> Q;
	Q.push({ 0,0 });	
	visited[0][0] = true;
	dist[0][0] = 1;
	while (!Q.empty()) {
		pair<int, int>cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			//cout << "들어옴" << endl;
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[nx][ny] || arr[nx][ny] != '1')continue;
			visited[nx][ny] = true;
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			Q.push({ nx,ny });
		}
	}

이 다음 문제에서 요구한 '각각의 수들은 붙어서 입력으로 주어진다.'을 유의하여
string 배열로 입력받고, string은 char형의 배열형태이니까 int형의 board의 2차원 배열처럼 이차원 배열 형태로 이용 할 수 있다.

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			board[i][j] = arr[i][j] - 48;

int형의 board 2차원 배열을 이용하고 싶으면 문자'0'은 ASCII code 값이 48이니
위와 같이 해주면 된다.

풀이

첫번째 풀이

#include<iostream>
#include<utility>
#include<queue>
#include<string>
using namespace std;

int board[100][100];
bool visited[100][100];
int dist[100][100];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string arr[100];

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
        	cin>>board[i][j];

	/*
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout<< board[i][j];
		cout << endl;
	}
	*/
	queue<pair<int, int>> Q;
	Q.push({ 0,0 });	
	visited[0][0] = true;
	dist[0][0] = 1;
	while (!Q.empty()) {
		pair<int, int>cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			//cout << "들어옴" << endl;
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[nx][ny] || board[nx][ny] != 1)continue;
			visited[nx][ny] = true;
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			Q.push({ nx,ny });
		}
	}

	cout << dist[n - 1][m - 1] << endl;
}

두번째 풀이

#include<iostream>
#include<utility>
#include<queue>
#include<string>
using namespace std;

bool visited[100][100];
int dist[100][100];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string arr[100];

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	/*
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout<< arr[i][j];
		cout << endl;
	}
	*/
	queue<pair<int, int>> Q;
	Q.push({ 0,0 });	
	visited[0][0] = true;
	dist[0][0] = 1;
	while (!Q.empty()) {
		pair<int, int>cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			//cout << "들어옴" << endl;
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[nx][ny] || arr[nx][ny] != '1')continue;
			visited[nx][ny] = true;
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			Q.push({ nx,ny });
		}
	}

	cout << dist[n - 1][m - 1] << endl;
}

번외

#include<iostream>
#include<utility>
#include<queue>
#include<string>
using namespace std;

int board[100][100];
bool visited[100][100];
int dist[100][100];

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	string arr[100];

	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			board[i][j] = arr[i][j] - 48;

	/*
	cout << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			cout<< board[i][j];
		cout << endl;
	}
	*/
	queue<pair<int, int>> Q;
	Q.push({ 0,0 });	
	visited[0][0] = true;
	dist[0][0] = 1;
	while (!Q.empty()) {
		pair<int, int>cur = Q.front(); Q.pop();
		for (int dir = 0; dir < 4; dir++) {
			//cout << "들어옴" << endl;
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m)continue;
			if (visited[nx][ny] || board[nx][ny] != 1)continue;
			visited[nx][ny] = true;
			dist[nx][ny] = dist[cur.first][cur.second] + 1;
			Q.push({ nx,ny });
		}
	}

	cout << dist[n - 1][m - 1] << endl;
}