[c++ | 백준] 2178번 미로 탐색

c++ 문제 풀이

 

 

 

 

---

 

 

[백준 2178번 미로 탐색 문제]

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

 

 

 

 

---

 

 

 

전체 풀이 코드

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

int row = 0, col = 0;
char arr[100][100];
int visited[100][100] = { {-1,} };

queue<pair<int, int>> q;

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

void BFS(int x, int y)
{
    q.push({ x,y });
    visited[x][y] = 1;

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

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

            if (nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
            if (arr[nx][ny] == '1' && visited[nx][ny] == 0)
            {
                q.push({ nx, ny });
                visited[nx][ny] = visited[x][y] + 1;
            }
        }
    }
}

int main(void)
{
    cin >> row >> col;
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
            cin >> arr[i][j];
    }

    BFS(0, 0);

    if (row > 0 && col > 0)
        cout << visited[row - 1][col - 1];

    return 0;
}

 

 

 

풀이 설명

천천히 풀이를 설명해보도록 하겠습니다. 먼저 전역 변수에 관한 설명입니다.

 

1. 전역 변수

int row = 0, col = 0; // 처음에 입력받는 n과 m
char arr[100][100]; // n * m 크기로 입력받는 입력값
int visited[100][100] = { {-1,} }; // 몇 번째로 방문한 곳인지 계산하기 위한 배열

queue<pair<int, int>> q; // 방문할 곳들이 쌓이는 큐

// 상 하 좌 우를 검사하기 위한 배열
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

 

 

그 다음으로 BFS 함수를 나누어 설명 드리겠습니다.

 

2.  BFS

void BFS(int x, int y)
{
    q.push({ x,y });
    visited[x][y] = 1;
}

맨 처음 출발지가 되는 곳은 가장 먼저 방문해야 하므로 queue에 넣어준 뒤 1번째로 방문한 곳이라고 visited에 표시하여 줍니다.

 

while (!q.empty())
{
     int x = q.front().first;
     int y = q.front().second;
     q.pop();
}

queue가 비지 않았을 때까지 while문을 실행하여 줍니다. 변수 x, y에 queue의 가장 앞에 있는 값을 넣어준 다음 q의 맨 앞 값을 방문 하였으니 queue에서 맨 앞 값을 빼줍니다.

 

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

 

for문을 4번(상 하 좌 우) 돌면서 지금 방문한 곳과 인접한 곳들을 찾아 queue에 넣어줄겁니다.

먼저 다음 방문할 곳의 x, y를 nx, ny로 구해줄건데요, 이를 예시를 들어 설명해보겠습니다.

 

현재 i가 0이라면 지금 방문한 x에 dx[i]를 더했을 때 x + 1이 되므로 지금 방문한 곳에 아래쪽의 x값이 나오게 됩니다. 똑같이 지금 방문한 y에 dy[i]를 더해주면 y + 0이기 때문에 지금 방문한 y값이 나오게 됩니다.

따라서 최종적으로 나온 nx, ny를 통해 지금 방문한 곳의 아래쪽을 검사하게 되는 것 입니다.

이렇게 상, 하, 좌, 우를 각각 검사해줍니다.

 

for (int i = 0; i < 4; ++i)
{
	if (nx < 0 || ny < 0 || nx >= row || ny >= col) continue;
	if (arr[nx][ny] == '1' && visited[nx][ny] == 0)
	{
		q.push({ nx, ny });
		visited[nx][ny] = visited[x][y] + 1;
	}
}

nx와 ny를 구해준 뒤에 첫 번째 if문에서 nx와 ny가 배열의 범위를 벗어나지 않았는지 검사하고 만약 범위에서 벗어났다면 continue를 해줍니다.

다음 if문에서는 arr[nx][ny]가 1인지 검사합니다. 즉 갈 수 있는 길인지 검사 해주고 nx, ny를 방문하지 않았는지 visited[nx][ny]를 통해 검사해줍니다.

 

위의 if문을 모두 통과했다면 queue에 nx, ny를 넣어주고 다음에 방문할 곳인 visited[nx][ny]를 지금 visited[x][y]에 +1을 해줍니다.

이렇게 해주는 이유는 다음의 갈 곳이 몇 번째로 방문한 곳인지 알기 위해서 인데요. 예시를 들어 설명해드리겠습니다.

 

 

현재 방문한 곳이 왼쪽의 사진에서 시작 지점인 0,0이라고 해봅시다.

 

시작 지점은 위에서 설명 드렸듯이 visited값을 1로 바꾸어 주었기 때문에 visited값을 1로 가지고 있을 겁니다.

 

시작 지점에서 상, 하, 좌, 우 중 갈 수 있는 길은 아래쪽만이 존재하기 때문에 아래쪽의 visited값은 현재 방문한 곳의 visited인 1 + 1이 됩니다.

 

이렇게 계속하여 visited값을 현재 방문한 곳 + 1을 다음에 방문할 곳에 넣어주면 마지막 도착 지점이 몇 번만에 도착한지 알 수 있게 됩니다.

 

 

3. 답 출력

if (row > 0 && col > 0)
	cout << visited[row - 1][col - 1];

이를 통해 구하려는 도착 지점을 몇 번째 만에 도달하게 되는지 출력하기 위해서 row-1, col-1지점의 visited값을 출력해주면 됩니다.

 

---

 

BFS로 백준 2178번 문제를 해설해 보았습니다.

혹시나 이해가 안되는 부분이 있으시다면 댓글을 남겨 주시면 답글을 통해 알려드리도록 하겠습니다.