[이코테] 미로 탈출(DFS/BFS) - 예제 5-11

문제

 

N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력

• 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

출력

• 첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

입력 예시
5 6
101010
111111
000001
111111
111111

출력 예시
10

 

 

정리

최단거리 -> BFS

1. dist[][] 만들어줘서 최단 거리 숫자 기록용

2. bool check[][] 만들어줘서 갔었는지 안갔었는지 확인용

3. return 마땅치 않으면 int bfs()로 정의 후 cout에 bfs(0,0) 넣는 아이디어 

 

 

 

내 풀이

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;

int n, m;

int a[200][200];
int d[200][200] = {0,};
bool check[200][200];

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };


int bfs(int x,int y) {
	
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	check[x][y] = true;
	d[0][0] = 1;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		

		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (0 <= nx && nx < n && 0 <= ny && ny < m)
			{
				if (a[nx][ny] == 1&&check[nx][ny]==false)
				{
					check[nx][ny] = true;
					d[nx][ny] = d[x][y] + 1;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
	
	return d[n - 1][m - 1];

	
}
int main() {
	
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
		{
			scanf("%1d", &a[i][j]);
			
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
		{
			if (a[i][j] == 1 && d[i][j] == 0)
			{
				bfs(i, j);
			}

		}
	}
	
	cout << bfs(0,0)<<endl;
	
	return 0;
}

 

 

정답 풀이

#include <bits/stdc++.h>

using namespace std;

int n, m;
int graph[201][201];

// 이동할 네 가지 방향 정의 (상, 하, 좌, 우) 
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int bfs(int x, int y) {
    // 큐(Queue) 구현을 위해 queue 라이브러리 사용 
    queue<pair<int, int> > q;
    q.push({x, y});
    // 큐가 빌 때까지 반복하기 
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        // 현재 위치에서 4가지 방향으로의 위치 확인
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // 미로 찾기 공간을 벗어난 경우 무시
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            // 벽인 경우 무시
            if (graph[nx][ny] == 0) continue;
            // 해당 노드를 처음 방문하는 경우에만 최단 거리 기록
            if (graph[nx][ny] == 1) {
                graph[nx][ny] = graph[x][y] + 1;
                q.push({nx, ny});
            } 
        } 
    }
    // 가장 오른쪽 아래까지의 최단 거리 반환
    return graph[n - 1][m - 1];
}

int main(void) {
    // N, M을 공백을 기준으로 구분하여 입력 받기
    cin >> n >> m;
    // 2차원 리스트의 맵 정보 입력 받기
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &graph[i][j]);
        }
    }
    // BFS를 수행한 결과 출력
    cout << bfs(0, 0) << '\n';
    return 0;
}