[프로그래머스 C++] 게임 맵 최단거리

 

[프로그래머스 C++] 게임 맵 최단거리

 

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

---

 

 

해결전략

 

BFS 너비우선탐색

 

---

 

 

처음시도한 코드

 

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

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

queue<pair<int,int>> Q;
int ch[101][101];

int solution(vector<vector<int> > maps)
{
    int answer = 0;

    Q.push({ 0, 0 }); // 시작점
    ch[0][0] = 1;

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

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

            if (ny < 0 || maps.size() <= ny || nx < 0 || maps[0].size() <= nx || maps[ny][nx] == 0) continue;

            if (ch[ny][nx] == 0 && maps[ny][nx]==1)
            {
                ch[ny][nx] = 1;
                Q.push({ ny, nx });

                answer++;

                if (ny == maps.size() - 1 && nx == maps[0].size() - 1)
                    return answer;
            }
        }
    }

    return -1;
}

 

틀린 부분

• 최단거리를 구해야 하는데 위의 코드에서 answer는 방문한 셀의 수를 계산하고 있다. 각 셀에 대해 BFS 탐색을 할 때마다 1씩 증가한다. 그러나 이렇게 하면 최단 경로를 찾는 것이 아니라 단지 모든 방문 가능한 셀을 세는 것이 된다.
• BFS 알고리즘은 시작점에서 다른 모든 점까지의 최단 거리를 찾는다. 각 단계에서 거리를 계산하려면 현재 위치에서 다음 위치로 이동할 때마다 거리가 1씩 증가해야 한다.
• dist[ny][nx] = dist[y][x] + 1;와 같은 코드를 사용하여 현재 위치 (dist[y][x])에서 다음 위치 (dist[ny][nx])로 이동할 때마다 거리를 누적해야 한다.

 

---

 

 

 

코드

 

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

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

queue<pair<int,int>> Q;
int dist[101][101];

int solution(vector<vector<int> > maps)
{
    Q.push({ 0, 0 }); // 시작점
    dist[0][0] = 1; // 시작

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

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

            if (ny < 0 || maps.size() <= ny || nx < 0 || maps[0].size() <= nx || maps[ny][nx] == 0) continue;

            if (maps[ny][nx] == 1 && dist[ny][nx] == 0)
            {
                dist[ny][nx] = dist[y][x] + 1;
                Q.push({ ny, nx });

                if (ny == maps.size() - 1 && nx == maps[0].size() - 1)
                    return dist[ny][nx];
            }
        }
    }

    return -1;
}

 

dist[2][3]=8이 dist[1][4]=10 보다 먼저 dist[2][4]를 방문했기 때문에  

dist[2][4]=9가 되고 dist[2][4]==0이 아니기 때문에 

dist[1][4]=10 위치에서 dist[2][4]로 방문하지 않는다.

 

 

 

 

 

---

 

유사문제

 

https://designerd.tistory.com/entry/%EB%B0%B1%EC%A4%80-2206%EB%B2%88-CC-%EB%8B%A8%EC%A7%80-%EB%B2%88%ED%98%B8-%EB%B6%99%EC%9D%B4%EA%B8%B0

[백준 2667번 C/C++] 단지 번호 붙이기

 

 

심화문제

https://designerd.tistory.com/entry/%EB%B0%B1%EC%A4%80-2206%EB%B2%88-CC-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0

[백준 2206번 C/C++] 벽 부수고 이동하기