BaekJoon 2178번: 미로 탐색

풀이법

BFS를 이용해서 문제를 해결하였다. 움직일수 있는 count를 queue의 매개변수로 넣어서 계산을 편히 하도록 설계하였다.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int vx[4] = { 1,0,-1,0 };
int vy[4] = {0,-1,0,1};
int arr[101][101];
bool visited[101][101];
int n, m;
void bfs(int x, int y, int count)
{
	queue<pair<int, pair<int, int>>> q;
	visited[x][y] = true;
	q.push({ x,{y,count} });
	while (!q.empty())
	{
		int tempx = q.front().first;
		int tempy = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();
		if (tempx == n && tempy == m)
		{
			cout << cnt;
		}
		for (int i = 0; i < 4; i++)
		{
			int tx = tempx + vx[i];
			int ty = tempy + vy[i];
			if (tx < 1 || tx>n || ty<1 || ty>m)
				continue;
			if (visited[tx][ty])
				continue;
			if (arr[tx][ty] == 1)
			{
				visited[tx][ty] = true;
				q.push({ tx,{ty,cnt + 1} });
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < s.length(); j++)
		{
			arr[i][j + 1] = s[j] - '0';
		}
	}
	bfs(1,1,1);
}

한계점 및 개선사항 (+주의사항)

직접 tx, ty배열을 만들어서 경우의 수를 지정하는 부분과 아래 부분 순서를 헷갈리지 않는 것이 중요하다. 들어올 수 있는 값의 범위에 있는지 확인하지 않고, visited 배열이나 arr 배열을 확인하게 되면 overflow가 발생할 수 있으니 주의하자

int vx[4] = { 1,0,-1,0 };
int vy[4] = {0,-1,0,1};	

for (int i = 0; i < 4; i++)
{
	int tx = tempx + vx[i];
	int ty = tempy + vy[i];
    if (tx < 1 || tx>n || ty<1 || ty>m)
    	continue;
    if (visited[tx][ty])
    	continue;
    if (arr[tx][ty] == 1)
    {
        visited[tx][ty] = true;
        q.push({ tx,{ty,cnt + 1} });
    }
}

 

github.com/pearlcrum/CodingTest/tree/main

pearlcrum/CodingTest