[백준 2178번] 미로 탐색 C++ 풀이

시간 제한

1초

메모리 제한

192MB

문제

N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

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

출력

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

내 풀이

#include<bits/stdc++.h>
using namespace std;
#define X first;
#define Y second;
char board[105][105] = { 0 };
int visit[105][105] = { 0 };
int dist[105][105] = { 0 };
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1};
int N(0), M(0);
queue<pair<int, int>> Q;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			board[i][j] = s[j]; // string으로 받아서 그냥 char 그대로 board에 넣는다.
		}
	}
	visit[0][0] = 1;
	dist[0][0] = 1;
	Q.push(make_pair(0, 0));
	while (!Q.empty()) {
		pair<int, int> cur = Q.front();
		Q.pop();
		int x = cur.X;
		int y = cur.Y;
		for (int dir = 0; dir < 4; dir++) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
			if (visit[nx][ny] || board[nx][ny] != '1') continue;
			visit[nx][ny] = 1;
			dist[nx][ny] = dist[x][y] + 1;
			Q.push(make_pair(nx, ny));
		}
	}
	cout << dist[N-1][M-1] << "\n";
}

위 코드를 보면 알겠지만 #define을 할 때 뒤에 세미콜론(;)을 붙이는 우를 범했다.
그래서 코드를 돌릴 때 cur.X와 cur.Y가 잘 동작하지 않았는데, 한참을 원인을 몰라 헤매다가 결국 int 변수를 또 따로 만들어서 거기에 넣고 계산을 하는 것으로 해결을 했었다.
또 이번 문제에서는 입력이 공백없이 주어져서 이를 처리하느라 고민이 많았다.
결론적으로 string은 문자들이 배열에 이미 들어가있는 것과 마찬가지이므로 string으로 받아서 board[i][j]에 채워넣었다.
이 때 숫자들은 int가 아니라 char이므로 굳이 int로 다시 바꾸지 않고 이후의 비교에서 모두 char형을 사용하였다.
또한 마지막칸까지의 거리 dist[N -1][M -1]를 출력하는 것도 아무 생각 없이 dist[N][M]을 출력했다가 맞왜틀?!만 외쳤었다.

바킹독님 풀이(출처)

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
string board[102];
int dist[102][102];
int n,m;
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);
  cin >> n >> m;
  for(int i = 0; i < n; i++)
    cin >> board[i];
  for(int i = 0; i < n; i++) fill(dist[i],dist[i]+m,-1);
  queue<pair<int,int> > Q;
  Q.push({0,0});
  dist[0][0] = 0;
  while(!Q.empty()){
    auto cur = Q.front(); Q.pop();
    for(int dir = 0; dir < 4; dir++){
      int nx = cur.X + dx[dir];
      int ny = cur.Y + dy[dir];
      if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
      if(dist[nx][ny] >= 0 || board[nx][ny] != '1') continue;
      dist[nx][ny] = dist[cur.X][cur.Y]+1;
      Q.push({nx,ny});
    }
  }
  cout << dist[n-1][m-1]+1; // 문제의 특성상 거리+1이 정답
}

위의 내 코드에서는 vis와 dist 변수를 따로 놨는데, dist의 초기값을 -1로 하면 vis 변수를 생성할 필요 없이 dist 하나로 거리와 방문여부까지 저장할 수 있다.