Lv.2 / 방문 길이

문제

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

프로그래머스

---

 

코드

#include <string>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

bool vis[4][11][11]; // 상 우 하 좌

int solution(string dirs) {
    int answer = 0;
    int r = 5, c = 5;
    int nr, nc;
    int dir;
    
    for(int i=0; i<dirs.size(); i++){
        dir = (dirs[i] == 'U' ? 0 : dirs[i] == 'R' ? 1 : dirs[i] == 'D' ? 2 : 3);
        
        if(dirs[i] == 'U') {
            nr = r - 1;
            nc = c;
        } else if(dirs[i] == 'D') {
            nr = r + 1;
            nc = c;
        } else if(dirs[i] == 'R') {
            nr = r;
            nc = c + 1;
        } else {
            nr = r;
            nc = c - 1;
        }
        
        if(nr < 0 || nc < 0 || nr >= 11 || nc >= 11) continue;
        
        // {r, c} 에서 dir 방향 == {nr, nc} 에서 (dir+2)%4 방향
        // dir 과 (dir+2)%4 는 서로 반대 방향
        if(!vis[dir][r][c] && !vis[(dir+2)%4][nr][nc]) {
            vis[dir][r][c] = true;
            vis[(dir+2)%4][nr][nc] = true;
            answer++;
        }
        
        r = nr;
        c = nc;
    }
    
    return answer;
}

---

 

풀이

이 문제에서 중요하게 생가했던 부분은 이미 방문한 길인지 확인하는 것이다.

 

특정 위치 {r, c} 에서 주어진 명령대로 {nr, nc} 로 이동하면 반드시 반대 방향으로 {nr, nc} 에서 {r, c} 로 이동한 적이 있는지 확인을 해줘야 한다. 

이를 위해서 방문 기록을 위한 vis 배열을 3차원으로 구성해주었다. 각 방향마다 기록을 해야하기에 3차원에서는 4만큼, 전체 좌표계의 길이가 11x11 이기에 1, 2차원에서는 11만큼 주었다.