프로그래머스 - 방문 길이 (C++)

Pixabay로부터 입수된 Liz Dunbar님의 이미지 입니다.

 

---

 

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

프로그래머스

 

 이번 문제는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5) 정도의 크기의 평면 위에서 캐릭터의 이동 경로가 주어질 때, 캐릭터가 처음 가 보는 길의 길이를 구하는 문제이다. 캐릭터는 (0, 0)에서 시작하며 평면을 벗어나는 이동 명령어는 무시한다. 

 캐릭터를 이동시키는 것은 크게 어렵지 않다. 방향에 따라 좌표를 수정시키기만 하면 된다. 그렇기에 이 문제의 핵심은 지나간 길을 어떻게 체크하느냐일 것이다. 처음에는 단순히 3차원 배열을 선언하여 문제를 풀었었다.

bool visited[MAX][MAX][4];	// visited[a][b][dir] => (a, b)를 dir 방향으로 왔다면 true

예를 들어, (2, 2)에서 (1, 2)로 위로 이동했다면, visited[1][2][위] == true일 것이다. 이렇게 풀었더니 테스트 케이스 8번부터 모두 오답이라고 나왔다. 그래서 지나간 길을 체크하는 방식이 틀렸다는 것을 깨달았다. 만약 (2, 2)에서 (1, 2)로 위로 이동한 후 다시 (1, 2)에서 (2, 2)로 아래로 이동하는 경우가 있다고 하자. 이 경우, visited[2][2][아래] == false이기에 이 역시 지나가지 않았던 길로 체크해버릴 것이다. 그렇기에 각 점만 체크하는 것이 아닌, 길을 정확히 체크해야 한다. 그래서 배열 visited를 아래처럼 수정하였다.

 

bool visited[MAX][MAX][MAX][MAX];   // visited[a][b][x][y] => (a, b) => (x, y) 경로를 지났다면 true

이 visited는 4차원 배열로, (a, b)에서 (x, y)로 이동한 경우 visited[a][b][x][y]와 visited[x][y][a][b]는 true가 된다. 즉, (2, 2)에서 (1, 2)로 이동했다면 visited[2][2][1][2]와 visited[1][2][2][2] == true가 된다. 그리고 다시 (1, 2)에서 (2, 2)로 이동해도 이미 visited[1][2][2][2]는 true이기에 중복 체크를 하지 않을 것이다. 

 그리고 배열의 인덱스로 음수는 불가능하기에 (-5, -5)를 (0, 0)으로 간주하였다. 즉, 문제를 풀기 위한 시작 좌표는 (0, 0)이 아니라 (5, 5)가 된다. 이것들을 고려한 코드는 다음과 같다.

 

#include <string>
#define MAX 11
#define DOWN 0
#define UP 1
#define LEFT 2
#define RIGHT 3
using namespace std;

bool visited[MAX][MAX][MAX][MAX];   // visited[a][b][x][y]: true => (a, b) => (x, y) 경로를 지났음
int nr[4] = { 1, -1, 0, 0 };
int nc[4] = { 0, 0, 1, -1 };

int Direction(char dir)
{
    switch(dir)
    {
        case 'D':
            return DOWN;
        case 'U':
            return UP;
        case 'L':
            return LEFT;
        case 'R':
            return RIGHT;
        default:
            return -1;
    }
}

bool IsInside(int r, int c)
{
    return 0 <= r && r < MAX && 0 <= c && c < MAX;
}

int solution(string dirs) {
    int answer = 0;
    
    int curR = 5;
    int curC = 5;
    
    for (int i = 0; i < dirs.length(); ++i)
    {
        int dir = Direction(dirs[i]);
        
        int nxtR = curR + nr[dir];
        int nxtC = curC + nc[dir];
        
        if (IsInside(nxtR, nxtC) == false)
            continue;
        
        if (visited[curR][curC][nxtR][nxtC] == false)
        {
            visited[curR][curC][nxtR][nxtC] = true;
            visited[nxtR][nxtC][curR][curC] = true;
            ++answer;
        }
        
        curR = nxtR;
        curC = nxtC;
    }
    
    return answer;
}