개발기록장

방문 길이

8 min read

문제 링크
난이도 : Lv. 2

문제 내용

문제 설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, “ULURRDLLU”로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. (8, 9번 명령어에서 움직인 길은 2, 3번 명령어에서 이미 거쳐 간 길입니다) 단, 좌표평면의 경계를 넘어가는 명령어는 무시합니다. 예를 들어, “LULLLLLLU”로 명령했다면 1번 명령어부터 6번 명령어대로 움직인 후, 7, 8번 명령어는 무시합니다. 다시 9번 명령어대로 움직입니다. 이때 캐릭터가 처음 걸어본 길의 길이는 7이 됩니다. 명령어가 매개변수 dirs로 주어질 때, 게임 캐릭터가 처음 걸어본 길의 길이를 구하여 return 하는 solution 함수를 완성해 주세요. 제한사항 dirs는 string형으로 주어지며, ‘U’, ‘D’, ‘R’, ‘L’ 이외에 문자는 주어지지 않습니다. dirs의 길이는 500 이하의 자연수입니다.

문제 분석

명령받은 커맨드랑 그 당시의 위치를 기억했다가 또 반복되면 안움직이게 하면 됨

근데 간과한 게 있었음.
내가 이동하면 그 반대편에서 이쪽으로 이동하는 것도 방문 처리를 해야 한다는 것이었음. 같은 명령을 무시하는게 아니라 같은 >>길<< 을 무시하는 거라서 그럼

작성한 코드

// 250407
 
#include <string>
#include <vector>
#include <iostream>
 
using namespace std;
 
pair<char, pair<int, int>> OppositeWay(char command, pair<int, int> nextPos) {
    pair<char, pair<int, int>> opWay = make_pair(command, nextPos);
    switch(opWay.first) {
        case 'U' :
            opWay.first = 'D';
            break;
        case 'D' :
            opWay.first = 'U';
            break;
        case 'R' :
            opWay.first = 'L';
            break;
        case 'L' :
            opWay.first = 'R';
            break;
    }
    return opWay;
} 
 
pair<int, int> Move(char command, pair<int, int> curPos) {
    // check that is in map
    pair<int, int> nextPos = curPos;
    switch(command) {
        case 'U' :
            nextPos.first--;
            break;
        case 'D' :
            nextPos.first++;
            break;
        case 'R' :
            nextPos.second++;
            break;
        case 'L' :
            nextPos.second--;
            break;
    }
    if(nextPos.first < -5 || nextPos.first > 5 || nextPos.second < -5 || nextPos.second > 5) 
        return curPos;
    else return nextPos;
}
 
int solution(string dirs) {
    // be careful 
    // 1. duplicated route is not in the final route count
    // 2. negative position allowed
    
    vector<pair<char, pair<int, int>>> visited;
    int count = 0;
    pair<int, int> curPos = make_pair(0, 0);
    
    for(char command : dirs) {
        pair<int, int> nextPos = Move(command, curPos);
        /* cout << "curPos : " << curPos.first << ", " << curPos.second << "  nextPos : " << nextPos.first << ", " << nextPos.second << " Command : " << command << endl;*/ 
        if(nextPos == curPos)
            continue;
        else {
            bool isDup = false;
            for(const auto &v : visited) {
                if(v.second == curPos && v.first == command){
                    /* cout << "Duplicated Route : " << v.second.first << ", " << v.second.first << " [" << v.first << "]" << endl; */
                    isDup = true;
                    break;
                }
            }
            if(!isDup) {
                count++;
                visited.push_back(make_pair(command, curPos));
                visited.push_back(OppositeWay(command, nextPos));
            };
            curPos = nextPos;
        }
    }
    
    return count;
}

  1. 선언부
    처음에 초기 위치를 0, 0으로 잡음
    그리고 방문한 길 목록인 visited를 선언함.
    visited는 (커맨드, (y, x)) 로 이루어져 있음.

  2. 움직임
    움직일 때 고려해야 하는 것 : 밖을 벗어나는가?
    중복 검사를 먼저 안하는 이유는 중복이라고 안움직이는건 아니기 때문임.
    밖을 벗어나버리면 그건 움직임 자체를 무시하니까 고려해야 함.
    그걸 Move 함수에서 구현했음.
    밖을 아예 나가버리면 기존 위치를 반환함으로써 이전과 달라진게 없다는 것으로 판단하려고 했음.

  3. 중복 검사 중복이면 움직이기만 하고 거리에 카운트는 안함.
    중복이 아니면 visited에 양방향으로 이동 경로 남겨줘야 함.

문제를 제대로 이해하는 습관을 들이자…
이번에 오래 걸린 이유도 “길”이라고 생각을 안하고 이동 경로만 생각해서 visited 저장을 단방향으로만 했다가 실패가 우중충 뜸.. (당연하지..)

우수 코드 분석

// 프로그래머스 책 참고
#include <string>
 
using namespace std;
 
bool visited[11][11][4];
 
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
 
int todir(char dir) {
    int ret;
    if (dir == 'U')
        ret = 0;
    else if (dir == 'R')
        ret = 1;
    else if (dir == 'D')
        ret = 2;
    else
        ret = 3;
    return ret;
}
 
bool isNotValid(int x, int y) { return x < 0 || y < 0 || x > 10 || y > 10;}
 
int opposite_direction(int dir) {return (dir + 2) % 4;}
 
int solution(string dirs) {
    int answer = 0;
    int x = 5, y = 5;
    for (auto c : dirs) {
        int dir = todir(c);
        int nx = x + dx[dir];
        int ny = y + dy[dir];
 
        if (isNotValid(nx, ny)) continue;
 
        if (visited[y][x][dir] == false) {
            visited[y][x][dir] = true;
            visited[ny][nx][opposite_direction(dir)] = true;
            answer ++;
        }
 
        x = nx;
        y = ny;
    } 
 
    return answer;
}

좌표 이동을 간편하게 하기 위해 dx, dy 리스트를 선언해 둔듯.
visited에서 [4]가 의미하는 바는 특정 방향으로 이동했는가?
저장되는 순서는 todir 확인하면 나옴. 나도 저렇게 해봐야지..

그래프 뷰