[프로그래머스] 아이템 줍기 C++

문제 링크

---

풀이

위 그림의 테두리를 다음의 조건에 따라 2차원배열로 만들어 주었다.
1. 빈 공간 = 0
2. 테두리 = 1
3. 사각형 안쪽 = -1

입력 rectangle에서 사각형을 하나씩 추가할 때마다 아래의 함수를 실행하였다.

void set_rec(int lx, int by, int rx, int ty)
{
    for (int y = by; y <= ty; ++y)
    {
        for (int x = lx; x <= rx; ++x)
        {
            if ((y == ty || y == by || x == lx || x == rx) && board[y][x] != -1)
                board[y][x] = 1;
            else
                board[y][x] = -1;
        }
    }
}

테두리좌표에는 1을 설정해주는데 주의할 점은 다른 사각형과 겹치는 부분은 무시한다.

모든 사각형을 추가해 맵을 완성하였다면 이 문제의 핵심적인 아이디어는 끝났다.

이제 출발점(캐릭터)과 도착점(아이템)의 최단거리만 구해주면 된다. bfs를 쓰면 쉽게 해결될 듯하다.

과연 그럴까?

위 그림을 보면 빨간점에서 파란점까지는 17이라는 수가 나와야 한다. 그러나 몇 번을 돌려봐도 15가 나온다. 이 부분에서 꽤 많이 시간을 할애해야 했다...

위 그림에서 빨간화살표가 잘못된 진행이다.

bfs에서 다음의 조건이 만족하면 다음좌표로 이동한다.
1. (nextX, nextY)까지의 거리가 1
2. board[nextY][nextX] == 1

(3,5)와 (3,6)은 이 조건을 만족하지만 이는 올바른 경로가 아니다...

내 경우 다음과 같은 방법으로 이 문제를 해결하였다.

(3,5)와 (3,6) 사이에 (3, 5.5)좌표를 추가하는 것이다. 한 칸이 아니라 두 칸이 떨어진 것으로 생각하면 (3,5)와 (3,6)은 인접하지 않는다.

하지만 실수를 쓰면 코드가 복잡해지거나 계산에 오류가 있을 수 있기 때문에 모든 좌표를 두배로 늘려주는 방법을 썼다.

(3,5)는 (5, 9)로, (3, 6)은 (5, 11)로 재설정해주면 한칸이 아니라 두칸 떨어지게 된다.

• (좌표 * 2) - 1

---

#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

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

void set_rec(int lx, int by, int rx, int ty)
{
    for (int y = by; y <= ty; ++y)
    {
        for (int x = lx; x <= rx; ++x)
        {
            if ((y == ty || y == by || x == lx || x == rx) && board[y][x] != -1)
                board[y][x] = 1;
            else
                board[y][x] = -1;
        }
    }
}

void bfs(int start_x, int start_y)
{
    fill(&dist[0][0], &dist[100][101], -1);
    queue<pair<int, int>> q;
    q.push({start_x, start_y});
    dist[start_y][start_x] = 0;
    
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; ++i)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (dist[ny][nx] != -1 || board[ny][nx] != 1)
                continue;
            
            q.push({nx, ny});
            dist[ny][nx] = dist[y][x] + 1;
        }
    }
}

int solution(vector<vector<int>> rectangle, int characterX, int characterY, int itemX, int itemY)
{
    for (int i = 0; i < rectangle.size(); ++i)
        set_rec(rectangle[i][0] * 2 - 1, rectangle[i][1] * 2 - 1, rectangle[i][2] * 2 - 1, rectangle[i][3] * 2 - 1);
    
    bfs(characterX * 2 - 1, characterY * 2 - 1);
    
    return dist[itemY * 2 - 1][itemX * 2 - 1] / 2;
}

코드를 보면 set_rec()과 bfs()는 그대로 쓰지만 solution()에서 모든 인자를 (좌표 * 2) - 1로 주는 것을 알 수 있다.

---

IDE를 쓰지 않으니 디버깅이 쉽지 않아 예외를 찾는데 꽤 오래 걸렸다. 실제 코딩테스트였다고 생각하면 아찔하다...