백준 2178 : 미로 탐색

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

---

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1

1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

---

생각

1. 세대가 있는 BFS
2. q에 따로 카운트 VS 세대로나누어서 카운트 -> 세대로나누어서 카운트   

---

코드

#include <bits/stdc++.h>

using namespace std;

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

int main()
{
    int n, m;

    cin >> n >> m;

    vector<string> map(n);
    vector<vector<bool>> visited(n, vector<bool>(m, false));

    for(int i = 0; i < n; i++)
    {
        cin >> map[i];
    }

    queue<pair<int, int>> q;

    pair<int, int> start = {0,0};

    q.push(start);

    visited[0][0] = true;

    int cx, cy, nx, ny;
    int count = 0;
    while(!q.empty())
    {
        count++;
        int qs = q.size();
        for(int i = 0; i< qs; i++)
        {
            cx = q.front().first;
            cy = q.front().second;

            q.pop();

            if(cx == n-1 && cy == m-1)
            {
                cout << count;
                return 0;
            }

            for(int d = 0; d < 4; d++)
            {
                nx = cx + dx[d];
                ny = cy + dy[d];

                if(nx < 0 || ny < 0 || nx >= n || ny >= m || visited[nx][ny])
                {
                    continue;
                }

                if(map[nx][ny] == '1')
                {
                    q.push({nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }
    }
}

---

틀린 이유

•  

---

수정 코드

 

---

결과

• 문제 풀이 시간 : 20 분
• 메모리 :  2028 KB
• 시간 :  0 ms

  ---

배운점 및 고칠점