[BaekJoon] 백준 2178번 미로탐색

[BaekJoon] 백준 2178번 미로탐색

 

문제: https://www.acmicpc.net/problem/2178

 

 

내코드

 

- 시작점으로부터 거리를 측정해야하는 전형적인 bfs로 풀면 되는 문제

- scanf_s를 visual studio에서 썼는데 백준에서는 scanf를 써서 풀었다.

- 무한대라는 의미에서 math.h를 include해서 INFINIFY를 써줬는데 0으로 출력되서 int 범위의 최대값인 2147483647을 초기 최소값으로 입력해줬다.

- dist를 저장하기 위해 queue에 값을 저장할때 이중 pair를 써줬다.

- 아래는 풀이를 위해 아이패드에 정리한 내용

 

백준 2178번 미로탐색.pdf

2.64MB

 

#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
#include <utility>

using namespace std;

int n, m, minDist = 2147483647;
int** arr;
bool** visited;
queue<pair<pair<int, int>, int>> qu;

int isNear(int p, int q, int dist) {
	if (p < 0 || q < 0 || p >= n || q >= m) return 0;
	if (arr[p][q] == 1 && visited[p][q] == false) {
		qu.push(make_pair(make_pair(p, q), dist + 1));
		visited[p][q] = true;
		return 1;
	}
	return 0;
}

int main(void)
{
	cin.tie(0);

	cin >> n >> m;
	arr = new int* [n];
	for (int i = 0; i < n; i++) {
		arr[i] = new int[m];
	}
	visited = new bool* [n];
	for (int i = 0; i < n; i++) {
		visited[i] = new bool[m];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%1d", &arr[i][j]);
			visited[i][j] = false;
		}
	}

	qu.push(make_pair(make_pair(0, 0), 1));
	visited[0][0] = true;

	while (!qu.empty()) {
		pair<pair<int, int>, int> cur = qu.front();
		qu.pop();
		int p = cur.first.first;
		int q = cur.first.second;
		int dist = cur.second;
		isNear(p, q - 1, dist);
		isNear(p - 1, q, dist);
		isNear(p, q + 1, dist);
		isNear(p + 1, q, dist);
		if (cur.first == make_pair(n - 1, m - 1)) {
			if (minDist > dist) {
				minDist = dist;
			}
		}
	}

	cout << minDist;

	return 0;
}

 

참고