문제 링크: 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

문제 풀이 과정

많이 풀어본 유형의 문제이기 때문에 푸는 과정에서 크게 어려움은 없었다.
이런 유형의 문제의 경우 자연스럽게 BFS의 활용이 떠올라야 한다.
DFS로도 풀 수는 있지만 출구를 찾을 때까지 완전 탐색의 방식이기 때문에 시간 복잡도가 높아진다.
넓게 갈 수 있는 step을 map 상에서 더해가면서 이 칸까지는 7step, 저 칸까지는 9step 이런식으로 숫자를 늘려가면서 모든 1이 있는 칸까지 이동한데 필요한 step 수를 적고 마지막에
출구 칸만 출력하면 된다.

코드를 보면 설명이 더 쉽다.

code(1) - input 받기

어쩌면 input을 받는 부분에서 흠칫했다 ㅎㅎ
1011011101 이런 값들이 다 붙어서 들어오기 때문이다.
이렇게 다 붙어서 들어오니 난 string으로 받아서 하나씩 분리, int로 바꿔서 matrix에 넣어줬다.

void input()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string temp;
		cin >> temp;
		for (int j = 0; j < m; j++)
		{
			map[i][j] = temp[j] - '0';
		}
	
	}
}

code(2) - BFS

codingtest 시리즈에서 앞에 풀었던 bfs와 다른 방식이 있다면
상하좌우로 이동하면서 그 map의 값이 0 이상인 경우(이동 가능한 경우) queue에 넣고
지금까지 이동해온 칸 수를 더해주었다.

void bfs()
{
	// start point = 0,0
	visited[0][0] = true;
	q.push({ 0,0 });
	
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++)
		{
			int x_step = x + dx[d];
			int y_step = y + dy[d];	
			if (!visited[x_step][y_step] and map[x_step][y_step] > 0 and x_step >= 0 and y_step >= 0 and x_step < n and y_step < m)
			{
				// not visited, map value is 1 and not out range of map
				visited[x_step][y_step] = true;
				q.push({ x_step, y_step });
				map[x_step][y_step] = map[x][y] + 1;
			}
		}
	}
}

전체 코드

#include <iostream>
#include <queue>

using namespace std;

//initialization
int n, m;
int map[101][101];
int visited[101][101];
queue <pair<int,int>> q;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

void input()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string temp;
		cin >> temp;
		for (int j = 0; j < m; j++)
		{
			map[i][j] = temp[j] - '0';
		}
	
	}
}

void bfs()
{
	// start point = 0,0
	visited[0][0] = true;
	q.push({ 0,0 });
	
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int d = 0; d < 4; d++)
		{
			int x_step = x + dx[d];
			int y_step = y + dy[d];	
			if (!visited[x_step][y_step] and map[x_step][y_step] > 0 and x_step >= 0 and y_step >= 0 and x_step < n and y_step < m)
			{
				// not visited, map value is 1 and not out range of map
				visited[x_step][y_step] = true;
				q.push({ x_step, y_step });
				map[x_step][y_step] = map[x][y] + 1;
			}
		}
	}
}
int main()
{
	input();
	bfs();
	cout << map[n-1][m-1];
	return 0;
}