문제 푼 날짜 : 2021-08-12

문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1844

접근 및 풀이

전형적인 BFS, DFS 문제였다.
BFS를 이용하여 출발지점에서 도착지점까지 벽유무, 방문여부, 범위를 체크하며 이동해주었다.
도착 시점에서 가장 적은 시간이 걸린 값을 반환해 주었다.

코드

#include <vector>
#include <queue>

using namespace std;

struct Point {
    int y, x, cnt;
};

#define INF 987654321

int solution(vector<vector<int> > maps)
{
    int answer = INF;
    int rowSize = maps.size(), colSize = maps.front().size();
    int dir[4][2] = {{ 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }};
    bool visited[101][101] = { false };
    
    queue<Point> q;
    q.push({ 0, 0, 1 });
    visited[0][0] = true;
    
    while (!q.empty()) {
        Point now = q.front();
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nextY = now.y + dir[i][0], nextX = now.x + dir[i][1];
            
            if (nextY == rowSize - 1 && nextX == colSize - 1) {
                answer = min(answer, now.cnt + 1);
                continue;
            }
            if (nextY < 0 || nextY >= rowSize || nextX < 0 || nextX >= colSize) {
                continue;
            }
            if (visited[nextY][nextX] == true || maps[nextY][nextX] == 0) {
                continue;
            }
            q.push({ nextY, nextX, now.cnt + 1 });
            visited[nextY][nextX] = true;
        }
    }
    
    if (answer == INF) {
        return -1;
    } else {
        return answer;
    }
}

결과

피드백

BFS 구현에 익숙해지고 있는 것 같다.