Imeamangryang | 게임 개발 기록

문제 링크

접근 방법

최단거리 문제 = BFS (Breadth-First Search)를 사용한다.
DFS는 최단거리 보장 안됨 (모든 경로를 탐색해야 함).

풀이 코드

text

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

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

int bfs(vector<vector<int> > &maps)
{
    queue<pair<int,int>> q; // 탐색을 위한 큐
    int n = maps.size(); // 맵의 행 크기
    int m = maps[0].size(); // 맵의 열 크기
    vector<vector<int>> table(n,vector<int>(m,0)); // 방문한 위치와 거리를 기록하는 테이블
    q.push({0,0}); // 시작 위치 큐에 삽입
    table[0][0] = 1; // 시작 위치 거리를 1로 초기화
    
     while(q.size()){
        pair<int,int> current = q.front();
        q.pop();
        for(int i = 0; i < 4; i++){ // 상, 우, 하, 좌 방향으로 탐색
            int ny = current.first + dy[i];
            int nx = current.second + dx[i];
            // 맵 범위를 벗어나거나, 벽을 만나거나, 이미 방문한 위치는 무시
            if(ny < 0 || nx < 0 || ny >= n || nx >= m || maps[ny][nx] == 0 || table[ny][nx]) 
                continue;
            table[ny][nx] = table[current.first][current.second] + 1; // 거리 업데이트
            q.push({ny,nx}); // 새 위치를 큐에 삽입
        }            
    }
    // 목표 지점에 도달한 경우 거리 반환, 그렇지 않으면 -1 반환
    return table[n - 1][m - 1] > 0 ? table[n - 1][m - 1] : -1;
}

int solution(vector<vector<int> > maps)
{
    int answer = bfs(maps);
    return answer;
}

해설

text

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

상, 우, 하, 좌로 이동하기 위한 방향 배열.

dy[i], dx[i]를 합치면 네 방향을 순서대로 탐색할 수 있음.

text

queue<pair<int,int>> q;
int n = maps.size();
int m = maps[0].size();
vector<vector<int>> table(n,vector<int>(m,0));

q: BFS 탐색을 위한 큐 (좌표 (y,x)를 저장).

n, m: 맵의 행과 열 크기.

table: 방문 체크 + 현재 위치까지의 이동 거리를 기록하는 테이블. (0이면 아직 방문 안 한 곳.)

text

q.push({0,0});
table[0][0] = 1;

시작 위치 (0,0)를 큐에 삽입하고, 이동 거리를 1로 설정한다. (0이 아니라 1로 시작하는 이유는 이동 칸 수를 셀 때 기준이 1이기 때문.)

BFS 루프

text

while(q.size()){
    pair<int,int> current = q.front();
    q.pop();

큐에서 현재 좌표를 꺼낸다.

text

for(int i = 0; i < 4; i++){
    int ny = current.first + dy[i];
    int nx = current.second + dx[i];

상, 우, 하, 좌 네 방향에 대해 탐색.

text

if(ny < 0 || nx < 0 || ny >= n || nx >= m || maps[ny][nx] == 0 || table[ny][nx]) 
    continue;

이동하려는 좌표가

맵 범위를 벗어났거나,
벽(maps[ny][nx] == 0)이거나,
이미 방문(table[ny][nx] != 0)한 경우, 무시.

text

table[ny][nx] = table[current.first][current.second] + 1;
q.push({ny,nx});

이동 가능하면,

거리를 현재 거리 + 1로 업데이트.
새 좌표를 큐에 삽입해서 다음 탐색 준비.

text

return table[n - 1][m - 1] > 0 ? table[n - 1][m - 1] : -1;

(n-1, m-1) 위치의 table 값이 0보다 크면, 최단 거리를 반환.
그렇지 않으면, 도달 불가능하다는 뜻이므로 -1 반환.