[BOJ] 2178 : 미로 탐색

Drakk·2021년 7월 10일

BFS C boj 다익스트라 알고리즘

알고리즘 문제풀이

목록 보기

2/22

💉문제 내용

문제 풀러가기

💉입출력

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

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

🔋예제 입출력

🔮예제 입력1
4 6
101111
101010
101011
111011
🔮예제 출력1
15

🔮예제 입력2
4 6
110110
110110
111111
111101
🔮예제 출력2
9

🔮예제 입력3
2 25
1011101110111011101110111
1110111011101110111011101
🔮예제 출력3
38

🔮예제 입력4
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111
🔮예제 출력4
13

💉문제 분석

🔋분류

BFS
다익스트라

🔋난이도

실버I

💉문제 풀이

🔋해법

문제는 다익스트라에 대한 기본이론을 알고계시다면, 50%는 이미 알고계신문제일겁니다.
이 문제의 핵심은 0은 지나갈수없기때문에 고려하지않으며, 오직 1인 배열만 고려합니다. (주석으로 별표친 부분이 해당부분입니다.)

🔋소스코드

#include <bits/stdc++.h>

#define MAX (101)
#define INF (987654321)

//arr : 배열, cost : 배열에서 해당부분에 대한 최소거리
int arr[MAX][MAX], cost[MAX][MAX];

void bfs(int M, int N, int sx, int se){
	int dx[4] = { 1, 0, 0, -1 };
	int dy[4] = { 0, 1, -1, 0 };
	std::queue<std::pair<int, int>>q;
	q.push(std::make_pair(sx, se));
	cost[0][0] = 0;
	
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		for(int i=0;i<4;++i){ //상하좌우 4방향을 차례대로 순회
			int newx = x + dx[i];
			int newy = y + dy[i];
		
			if(newx < 0 || newy < 0 || newx >= M || newy >= N ) continue;
			if(arr[newy][newx] == 1){ //오직 1일때에만 고려합니다.
            
            			//이 부분 익숙하신분 계실겁니다.
                        	//네, 다익스트라랑 매우 비슷합니다.
				if(cost[newy][newx] > cost[y][x] + 1){ /**/
					cost[newy][newx] = cost[y][x] + 1;
					q.push(std::make_pair(newx, newy));
				}
			}
		}
	}
}

int main() {
	int N, M;
	std::cin >> N >> M;
	for(int i=0;i<N;++i){
		std::string str;
		std::cin >> str;
		for(int j=0;j<M;++j){
			arr[i][j] = str[j] - '0'; //'0'을 빼는 이유는 아스키코드값에 따라 문자를 숫자로 바꾸기 위함입니다.
			cost[i][j] = INF;
		}
	}
	
	bfs(M, N, 0, 0);
    
   	//1을 더하는이유는 시작점때문입니다.
    	//시작점은 항상 1 이기때문이죠.
	std::cout << cost[N - 1][M - 1] + 1;
}