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

아주 제대로 뻘짓한 문제.

문제

문제에서 추출해야 하는 정보는 다음과 같다.

• 입력으로 방향이 들어오며, 방향에 따라 캐릭터는 상하좌우로 이동한다.
• 이때 처음 걸어본 길(선)의 길이(개수)를 구해야 한다.
• 즉 방문처리된 선을 모두 찾는 문제다.

제한사항

깔끔하다. 방향 입력이 들어오면 (5,5)에서 출발하여 이동한 총 간선의 개수를 출력하면 된다. 점이 아니라 선을 다루는 것에 주의해야 한다.

시행착오

맨 처음에 visited 2차원 배열로 호가롭게 시작했으나, 2차원으로는 4개의 방향을 나타내기 어려움을 직감하고 3차원 배열로 확장하는 것 까지는 괜찮았다. BFS를 떠올리며 범위 이탈에 대한 예외처리도 따로 해 주었다.

이 문제의 핵심은 바로 특정 위치에서 한쪽으로 이동한 간선은 그 이동한 위치에서 다시 원 위치로 향하는 간선과 동일하다는 것을 알아채는 것이다.

특정 칸에서 오른쪽으로 이동하는 간선을 사용했다면, 이동한 칸 기준에서 왼쪽으로 이동하는 것을 정답에 카운트하면 안 된다. 그러므로 특정 칸에서 오른쪽으로 이동하는 간선을 사용했는지 여부와 반대편에서 왼쪽으로 이동하는 간선을 사용했는지 여부를 모두 따져주어야 했다. 이걸 깨닫는 데 오랜 시간이 걸렸다..

반대편 방향에 해당하는 인덱스를 추출하여, 이동한 새 좌표의 간선도 방문처리해주어야 한다.

깨닫고 나서는 꽤 허무한 문제였다.
코테 푸는 속도가 너무 느린 것 같아 걱정이다.
더 열심히 해야겠다.

소스 코드

#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};

int solution(string dirs) {
    int answer = 0;
    bool visited[11][11][4]; // 특정 좌표에서 특정 방향으로 뻗는 간선의 사용여부
    memset(visited, false, sizeof(visited));
    
    int x = 5; // 출발점
    int y = 5; 
    
    for(int i=0; i<dirs.size(); i++){
        int dir = 0;
        char a = dirs[i];
        if(a == 'L'){ // 방향 결정
            dir = 0;
        } else if(a == 'U'){
            dir = 1;
        } else if(a == 'R'){
            dir = 2;
        } else {
            dir = 3;
        }
        
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        
        if(nx < 0 || ny < 0 || nx >= 11 || ny >= 11) continue;
        int countdir = (dir + 2) % 4; 
        if(!visited[x][y][dir] && !visited[nx][ny][countdir]){
            visited[x][y][dir] = true;
            visited[nx][ny][countdir] = true;
            answer++;
        }
        x = nx;
        y = ny;
    }
    
    return answer;
}

교훈

• "점" 뿐만 아니라 "선"을 다루는 것에도 익숙해져야 한다.
• 방향을 다루어야 하는 문제는 항상 더 깊게 고민하는 습관을 가지자.