2178 미로 탐색

2178 미로 탐색

가장 기본적인 BFS 경로 탐색 문제

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

문제

---

N X M 크기로 배열되는 미로.

미로에서 1은 이동 가능한 칸, 0은 벽

이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 때

지나야 하는 최소의 칸의 수를 구하는 문제

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다.

다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.

항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

문제 분석

---

필요 변수들

• 가로, 세로 int N, M
• 미로를 저장할 N, M 배열 int map[101][101]
• 배열의 방문여부를 저장할 같은 사이즈의 배열 int visited[101][101]
• 4방향을 표현할 2차원 배열 ↓→↑← 방향을 저장 int direct[4][2]
• BFS 탐색에 필요한 queue
• 몇칸 이동했는지 저장할 cost. 따로 전역변수로 둬도 되지만,
  y, x 좌표를 가진 구조체에 함께 처리했음 struct node

주의점

1. 각각의 수들은 붙어서 입력으로 주어진다
   • 101011과 같이 입력이 들어옴. int형으로 map[y][x] 에 저장하면
     1이 아닌 101011이 저장됨
   • char형으로 하나씩 입력받아 int로 변환해줬음.
     혹은 map을 char map으로 정의해도 될듯
2. 시작하는 칸과 끝나는 칸도 이동 칸수에 포함시켜야함.
3. (1,1)이 시작점이지만, 배열 특성상 (0,0)으로 시작했음.
   또한 도착점인 (N,M)도 한칸씩 당겨 (N-1, M-1)이 도착점이 되도록 설정함

의사 코드

1. 입력받기
2. BFS 시작
   • 시작점인 (0,0)을 큐에 넣고 방문처리
   • 큐가 빌때까지 아래를 반복
     • 큐의 맨 앞을 꺼낸다
     • 도착점인지 확인한다. 도착점이라면 현재 cost를 저장한다
     • 현재 지점에서 4방향으로 이동시도
       • 경계 체크
       • 벽인지 체크
       • 방문한곳인지 체크
       • 위 조건들을 통과했다면 방문 처리 후, cost를 1 증가시키고 큐의 맨 뒤에 넣는다
3. 저장된 cost를 출력한다

소스코드

---

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int map[102][102];
int visited[102][102] = { 0 };
int direct[4][2] = { 1,0, 0,1, -1,0, 0,-1 };

struct node {
	int y;
	int x;
	int cost;
};

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N >> M;

	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			char ch;
			cin >> ch;
			map[y][x] = (ch - '0');
		}
	}

	queue<node> qu;
	int res = 1;
	visited[0][0] = 1;
	qu.push({ 0,0,0 });

	while (!qu.empty()) {
		node now = qu.front();
		qu.pop();

		if (now.y == N - 1 && now.x == M - 1) {
			res = now.cost + 1; // 마지막칸 포함
		}

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			if (dy < 0 || dx < 0 || dy > N || dx > M) continue;
			if (map[dy][dx] == 0) continue;
			if (visited[dy][dx] == 1) continue;
			

			visited[dy][dx] = 1;
			qu.push({ dy, dx, now.cost+1 });

		}
	}

	cout << res;

	return 0;
}