코테 일기(9) : 백준 [2178번] 미로찾기(BFS)

이번에 풀 문제는 백준 2178번 미로찾기이다.

DFS, BFS는 꼭 알고 가야 하는 탐색기법이기에 풀어보기로 했다. 정답률은 35%로 충분히 풀만한 오기가 생겼다.

처음엔 실력도 모자란 내가 풀어도 될까? 라는 마음이 들었지만 언젠간 넘어가야 할 산이다.

처음 든 생각

DFS로 stack을 사용해서 푸는것이 더 편해 보였다. 

하지만 문제에서는 BFS를 요구했으니 넓이 탐색으로 풀기로 했다.

연속된 1을 통해 array의 마지막에 도달하는 것이 우리 최종 목표이다.

먼저 queue의 size가 0 이 아닌 한 반복을 해야 할 것이고 while (queue.size() > 0)

queue의 front를 받아와서 한 단계 씩 나아가야한다. (queue.front())

이후 상하좌우를 모두 검색하여 1이 존재하고 방문하지 않았다면 push시키고, 방문 flag를 바꿔줘야한다.

만약 이 과정 도중 queue의 마지막이 끝에 도착했다면 멈추고 (break)

depth를 출력한다. (depth는 처음부터 끝까지 도달하기 위해 거쳐온 횟수라는 생각이 들었다.)

코드

#include <iostream>

#include <queue>

#include <vector>

#include <stdio.h>

 

using namespace std;

 

typedef struct {

        int row;

        int col;

        int depth;

} Position;

 

int bfs_find(vector<vector<int> > arr) {

        vector<int> ar;

        Position p = { 0,0,1 };

        vector<vector<int> > check(arr.size(), vector<int>(arr[0].size(), 0));

        queue<Position> point;

       

        point.push(p);

 

        while (point.size() > 0) {

                

                 Position pos = point.front(); //현재 위치

                 int p = point.front().depth;

                

                  //깊이가 길어질수록 count++

                

                 point.pop(); //현재 위치를 찾았으니 pop시켜서 하나씩 밀기

 

                 if (pos.row<arr.size()-1 && arr[pos.row + 1][pos.col] == 1 && check[pos.row + 1][pos.col] == 0) { 

//밑에를 방문하지 않았고 1이라면

                         point.push({ pos.row + 1, pos.col,p+1}); //큐에 집어넣기(depth 1증가)

                         check[pos.row + 1][pos.col] = 1;

                         if (point.back().row == arr.size() - 1 && point.back().col == arr[0].size() - 1) { 

    //point의 끝이 N-1,M-1이라면

                                 break;

                         }

                 }

                 if (pos.col<arr[0].size()-1 && arr[pos.row][pos.col+1] == 1 && check[pos.row][pos.col+1] == 0) { 

//오른쪽을 방문하지 않았고 1이라면

                         point.push({ pos.row, pos.col+1,p+1}); //큐에 집어넣기(depth 1증가)

                         check[pos.row][pos.col + 1] = 1;

                         if (point.back().row == arr.size() - 1 && point.back().col == arr[0].size() - 1) { 

    //point의 끝이 N-1,M-1이라면

                                 break;

                         }

                 }

                 if (pos.row-1 >= 0 && arr[pos.row-1][pos.col] == 1 && check[pos.row-1][pos.col] == 0) { 

//위를 방문하지 않았고 1이라면

                         point.push({ pos.row-1, pos.col,p+1}); //큐에 집어넣기(depth 1증가)

                         check[pos.row - 1][pos.col] = 1;

                         if (point.back().row == arr.size() - 1 && point.back().col == arr[0].size() - 1) { 

    //point의 끝이 N-1,M-1이라면

                                 break;

                         }

                 }

                 if (pos.col - 1 >= 0 && arr[pos.row][pos.col-1] == 1 && check[pos.row][pos.col-1] == 0) { 

//왼쪽을 방문하지 않았고 1이라면

                         point.push({ pos.row, pos.col-1,p+1}); //큐에 집어넣기(depth 1증가)

                         check[pos.row][pos.col-1] = 1;

                         if (point.back().row == arr.size() - 1 && point.back().col == arr[0].size() - 1) { 

    //point의 끝이 N-1,M-1이라면

                                 break;

                         }

                 }

                 //만약 아무 곳도 방문할 곳이 없으면 while을 한번 더 돌게되고 다음 queue를 확인하게 됨

        }

        return point.back().depth;

}

 

int main() {

        int N, M;

        cin >> N >> M;

        vector<vector<int> > input(N,vector<int> (M,0));

        int a = 0;

        for (int i = 0; i < N; i++) {

                 for (int j = 0; j < M; j++) {

                         scanf("%1d", &a);

                         input[i][j] = a;

                 }

        }

        cout << bfs_find(input);

}

이번에는 코드의 가독성과 depth를 표현하기 위해 구조체를 사용했다.

대부분의 문법은 괜찮았지만 처음 생각했던 depth를 그대로 표현하니,

기존에 방문했던 곳까지 count가 되는 문제가 생겼다.

이를 해결하느라 애를 먹었던 것 같다.

하지만 이제 bfs, dfs는 문제를 어떻게 풀어야 할지는 확실히 알게 되어서 시간 단축을 할 수 있을 것 같다.

Visual Studio에서는 scanf를 무척 싫어한다.. scanf_s로 했다가 컴파일 에러까지 뜨고..

주석 처리를 못한 출력문들 때문에 틀렸다는 것 까지...

그거만 아니면 한번에 맞출 수 있었는데...

그래도 맞춘 사람들 메모리와 내 메모리가 같은 걸 보니 제대로 풀긴 했나보다.