2178 - 미로탐색

문제

코드

#include <bits/stdc++.h>
using namespace std;

const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};
int visited[104][104];
int a[104][104];
int n,m,y,x,ny,nx;

int main(){
	
	cin >> n >> m;
	
	for(int i=0; i<n; i++){
		for(int j =0; j <m; j++){
			scanf("%1d", &a[i][j]);
		}
	}
	
	queue<pair<int,int>>q;
	visited[0][0] = 1;
	q.push({0,0});
	while(q.size()){
		tie(y,x) = q.front(); q.pop();
		for(int i = 0; i < 4; i++){
			ny = y + dy[i];
			nx = x + dx[i];
			if(ny < 0 || ny >= n || nx < 0 || nx >= m || a[ny][nx] == 0 )continue;
			if(visited[ny][nx])continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ny,nx});
		}
	}
cout << visited[n-1][m-1];
return 0;
}

풀이

이동시 가중치가 같을 때 최단 거리를 구하는 알고리즘은 BFS를 이용해야한다.
노드가 한 레벨 증가할 때 거리를 하나씩 추가하면 되기 때문이다.
BFS 같은 경우는 queue를 이용해야한다.
또한 2차원의 배열이기 때문에 pair로 값을 설정해두었고
visited부터 코드를 보면 시작 위치를 방문했다는 의미의 visited 배열을 1로 설정.
첫 번째 값 큐에 담기.
큐 사이즈 만큼 반복 --> 이 부분이 인접한 노드들을 방문하는 과정이다.
미리 선언해둔 이동 좌표만큼 움직이며 방문 값을 1 증가 시킨다.
visited를 1증가 시킨다는 것은 이전 노드와 인접해있는 값 보다 1만큼 더 움직인다는 뜻이다. 다 돌았으면 다시 재귀로 이 값을 넣으면 된다.
마지막에 출력하고 싶은 위치 값을 출력하면 된다.

결과

후기

BFS의 알고리즘을 안다면 쉽게 해결할 수 있는 문제였다.
어느 상황에 BFS를 사용하면 좋을지 생각해보면 큰 어려움없이 풀 수 있다고 생각한다.