백준 2178번 미로탐색 (C++)

문제

최단 거리 이야기가 나온다는 것을 보고 bfs문제임을 알 수가 있다.

정답 코드

#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};
int main()
{
	int n,m;
	string s;
	ios :: sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	vector<vector<int>> arr(n + 1,vector<int>(m + 1,0));
	vector<vector<int>> vis(n + 1,vector<int>(m + 1,0));
	for (int i=0;i < n;i++)
	{
		cin >> s;
		for (int j=0;j < m; j++)
		{
			arr[i+ 1][j + 1] = s[j];
		}
	}
	queue <pair <int,int >> Q;
	Q.push({1,1});
	vis[1][1] = 1;
	while (!Q.empty())
	{
		pair<int,int> qu = Q.front();
		Q.pop();
		int X = qu.second;
		int Y = qu.first;
		if (Y == n && X== m)
		{
			cout << vis[Y][X] << "\n";
			return (0);
		}
		for (int i =0; i < 4;i++)
		{
			if (X + dx[i] <= 0 || X+ dx[i] > m || Y+dy[i] <=0 || Y+dy[i]>n)
				continue;

			if (vis[Y+dy[i]][X+dx[i]] == 0)
			{
				vis[Y+dy[i]][X+dx[i]] = vis[Y][X] + 1;
				if (arr[Y+dy[i]][X+dx[i]] == '1')
					Q.push({Y+dy[i],X+dx[i]});
			}
		}

	}

}

문제 풀이의 흐름

• 입력이 n개의 줄로 들어오니까 string으로 받아서 넣어주고 잘라서 넣어주고

• 1,1부터 보라해서 queue에 푸쉬해주고

• 큐가 빌 때까지 계속 반복하는데

• 만약 원하는 값에 도달했다면 출력하고 끝내고

• 레벨에 따라 값이 달라져야 하므로 vis에 방문한 레벨을 하나 더해서 레벨에 따라 횟수를 더해줬다.

• 인덱스를 벗어나는 경우 잘라줬고

• 방문하지 않은 경우만 푸쉬해주는데 1이 string 형식이라 비교를 char로 해준다.

• 우리가 갈 수 있는 곳은 육지인 곳도 있고 바다도 있어서 1인경우만 푸쉬를 해준다.

주의 할 점

X 와 Y의 위치를 주의하고 string 으로 한줄로 들어온다는 사실을 유념해야 한다.

그 외에는 bfs의 교과서라고 볼 수 있는 문제라서 코딩 테스트를 하러간다면 이정도는 눈 감고도 짜야만 한다.

인덱스가 벗어나거나 방문을 안 했거나 갈수 있는 미로가 아닌지에 대한 분기가 정확하게 되어야 합니다. 안 그러면 틀릴 가능성이 커요.

반성 및 고찰

일부러 벡터를 사용해서 문제를 풀었고 크기도 최대한 딱 맞췄다.

인덱스가 헷갈리니까 아에 제일 위를 1,1로 뒀는데 그게 더 안 헷갈려서 좋은 것 같다.

손코딩을 하니까 확실히 침착하게 문제를 풀수 있어서 좋은 것 같다.

손코딩

Uploaded by N2T