문제링크
https://www.acmicpc.net/problem/2178
문제
N×M크기의 배열로 표현되는 미로가 있다.
101111
101010
101011
111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
조건
- 시간 제한 : 1s
- 메모리 제한 : 192MB
해설
미로를 풀기 위해 BFS 그래프 탐색 알고리즘을 약간 변형하여 문제를 풀어줄 수 있다.
시작점에서 갈 수 있는 가까운 칸 순서로 칸들을 큐에 담으며 탐색해나간다. BFS 알고리즘과 다르게, visited 에 방문하였음을 기록하는게 아니라, 해당 칸까지 가는데 필요한 최소 이동 거리를 기록한다.
특정한 칸을 처음 방문한 경우 / 더 짧게 갈 수 있는 방법을 찾은 경우, 해당 칸에서 상하좌우로 이동하여 더 짧은 경로를 만들 수 있는 칸을 찾는다. 만약 주변에 경로가 짧아지는 칸이 있다면, 짧은 이동거리로 갱신하고 큐에 담아 해당 칸 주변을 반복해서 검사한다.
모든 갈 수 있는 짧은 경로를 찾은 다음 (큐가 비어있으면) 가고자 하는 (N, M) 칸에 가는 최소 이동거리를 출력해주면 된다.
풀이
먼저 필요한 자료구조를 선언하고 입력을 받아준다. map은 지도를 기록하는 2차원 배열이고, moves는 최소 이동거리를 기록하는 2차원 배열이다. moves 배열에 더 작은 값을 집어넣으면서 update를 해주게 되므로, 100x100지도에서 나올 수 없는 큰 값(나는 10001을 선택함)으로 초기화해준다.
int map[101][101] = {0, };
int moves[101][101];
int M, N;
int main() {
cin >> N >> M;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
scanf("%1d", &map[i][j]);
moves[i][j] = 10001;
}
}
moves[0][0] = 1;
// 계속 이어짐
}
각 칸까지의 최소 이동거리를 update 해주는 함수인 findPath 함수를 정의해준다. 코드에 대한 설명은 주석으로 달아두었다.
typedef pair<int, int> pos;
int xarr[4] = {0, 0, 1, -1};
int yarr[4] = {1, -1, 0, 0};
void findPath(pos start) {
// Queue 선언해서 시작점 담아주고
queue<pos> Q;
Q.push(start);
// Queue가 빌 때 까지 (더 갱신할 경로가 없을 때 까지) 반복
while(!Q.empty()) {
// Queue에서 top에 있는 값을 가져오고 pop하기
pos current = Q.front();
Q.pop();
// 상하좌우에 새로 경로를 갱신할 칸이 있으면 경로 갱신하고 Queue에 담기
for(int i = 0; i < 4; i++) {
// 범위 검사는 try catch문으로 타파해주었다.
try {
int currentMoves = moves[current.first][current.second];
pos next = make_pair(current.first+xarr[i], current.second+yarr[i]);
// 만약 next 칸에 길이 있고, current의 이동경로+1 이 next의 원래 이동경로보다 짧으면
// next의 이동경로를 current+1 로 update하고 Queue에 담아 새로 갱신할 길을 찾아준다.
if(map[next.first][next.second] == 1
&& moves[next.first][next.second] > currentMoves+1)
{
moves[current.first+xarr[i]][current.second+yarr[i]] = currentMoves+1;
Q.push(next);
}
}
catch (out_of_range &e) {
continue;
}
}
}
}
그리고 메인 함수에서 아래 코드를 실행시켜주면 원하는 결과를 얻을 수 있다. moves 배열이 10001으로 초기화되어 있으므로, 첫 칸의 이동 거리를 1로 set 해주고 [0, 0] 부터 시작하여 이동거리 찾기 함수를 실행해준다. 함수가 종료되면 특정 칸 까지의 최소 이동거리가 모두 담겨있으며, moves[N-1][M-1]에 담겨있는 N, M칸 까지의 최소 이동거리를 출력해주면 된다.
moves[0][0] = 1;
findPath({0, 0});
cout << moves[N-1][M-1] << '\n';
코멘트
이정도는 이제 쉽지 ㅎ
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define FAST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
typedef pair<int, int> pos;
int xarr[4] = {0, 0, 1, -1};
int yarr[4] = {1, -1, 0, 0};
int map[101][101] = {0, };
int moves[101][101];
int M, N;
void findPath(pos start) {
queue<pos> Q;
Q.push(start);
while(!Q.empty()) {
pos current = Q.front();
Q.pop();
for(int i = 0; i < 4; i++) {
try {
int currentMoves = moves[current.first][current.second];
pos next = make_pair(current.first+xarr[i], current.second+yarr[i]);
if(map[next.first][next.second] == 1
&& moves[next.first][next.second] > currentMoves+1)
{
moves[current.first+xarr[i]][current.second+yarr[i]] = currentMoves+1;
Q.push(next);
}
}
catch (out_of_range &e) {
continue;
}
}
}
}
int main() {
// FAST;
cin >> N >> M;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
scanf("%1d", &map[i][j]);
moves[i][j] = 10001;
}
}
moves[0][0] = 1;
findPath({0, 0});
cout << moves[N-1][M-1] << '\n';
return 0;
}
Uploaded by Notion2Tistory v1.1.0