[프로그래머스/Level 2] 방문 길이 (C++)

programmers.co.kr/learn/courses/30/lessons/49994

코딩테스트 연습 - 방문 길이

DP 문제인줄 알았는데 단순 구현 문제였습니다.

 

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

이전 문제와는 다르게 visit배열을 4차원으로 선언하여 점이 아닌 간선의 방문을 체크해야합니다. 또한 어느 방향으로 특정 간선을 지나던 해당 간선은 완전히 방문되었다고 처리하므로, 양방향으로 방문했다고 처리해줘야합니다.

그리고 좌표의 시작점이 (0, 0)이고 범위는 (-5, -5) ~ (5, 5) 인데, 간선의 방문을 체크하기 위해 인덱스를 음수를 사용할 수 없기 때문에, 시작점의 좌표를 (5, 5)로 옮기고, 범위를 (0, 0) ~ (10, 10)으로 위와 같이 수정하였습니다.

마지막으로 배열에서는 (0, 0)이 맨 왼쪽 위에서 시작되므로, 이를 시계 방향으로 90도 회전했다고 가정하고, 문제를 구현했습니다.

(예를들어 문제에서 U는 실제 배열에서는 R이 됩니다.)

 

#include <string>
using namespace std;

bool visit[11][11][11][11]; // 간선을 체크
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int solution(string dirs) {
    int answer = 0;
    int x = 5, y = 5; // 중점을 (0, 0) -> (5, 5)로 : 범위를 (0, 0) ~ (10, 10)으로 하려고
    
    for(int i = 0; i < dirs.size(); i++) {
        int nx = x, ny = y;
        if(dirs[i] == 'U') nx += dx[0], ny += dy[0];
        else if(dirs[i] == 'D') nx += dx[1], ny += dy[1];
        else if(dirs[i] == 'R') nx += dx[2], ny += dy[2];
        else nx += dx[3], ny += dy[3];
        
        if(nx < 0 || nx > 10 || ny < 0 || ny > 10) continue;
        if(!visit[x][y][nx][ny] && !visit[nx][ny][x][y]) {
            answer++;
            visit[x][y][nx][y] = true; // 방문처리를 양방향으로
            visit[nx][ny][x][y] = true;
        }
        
        x = nx, y = ny;
    }
    
    return answer;
}