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

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

프로그래머스

 

구현문제다. 방문 알고리즘이라고 봐야할까 싶다.

 

주어진 대로 이동하는 경로를 새야하는데 단순히 방문체크만해서는 풀 수 없다. 3차원 배열을 선언하고 A노드에는 4방향으로 들어올 수 있기 때문에 각 방향마다 방문체크를 해줘야한다.

 

그리고 중요한 것은

 

A -> B로 이동했다면 B -> A 도 지난 길이 되기 때문에 체크해놓아야한다. 이것을 눈치채지 못해 풀지 못했다..

 

#include <string>
#include <iostream>

using namespace std;

bool visited[11][11][4] = {false,};
int solution(string dirs) {
    int answer = 0;
    int x = 5;
    int y = 5;
    
    for(int i = 0; i < dirs.size(); i++){    
        char command = dirs[i];
        int c1 = -1;
        int c2 = -1;
        int nx = x;
        int ny = y;
        if(command == 'U'){
            c1 = 0;
            c2 = 1;
            nx--;
        }else if(command == 'D'){
            c1 = 1;
            c2 = 0;
            nx++;
        }else if(command == 'R'){
            c1 = 2;
            c2 = 3;
            ny++;
        }else if(command == 'L'){
            c1 = 3;
            c2 = 2;
            ny--;
        }
        
        if(nx < 11 && nx > -1 && ny < 11 && ny > -1){
            if(!visited[nx][ny][c1]){
                answer++;
                visited[nx][ny][c1] = true;
                visited[x][y][c2] = true;
            }
            
            x = nx;
            y = ny;
        }
    }
    
    return answer;
}