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

 

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

 

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

---

 

 

해결전략

 

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++] 단지 번호 붙이기

[백준 2667번 C/C++] 단지 번호 붙이기 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도

designerd.tistory.com

 

 

심화문제

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++] 벽 부수고 이동하기

[백준 2206번 C/C++] 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽

designerd.tistory.com