[C++] Programmers Lv. 2 "방문 길이"

🔵 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/49994?language=cpp

프로그래머스

 

💡 Point

• 특정 구역이 아닌 [한 구역에서 다른 구역으로 가는 길]을 구하는 것이다.
• 중복 경로는 무시한다.

 

🔷 특정 구역이 아닌 [한 구역에서 다른 구역으로 가는 길]을 구하는 것이다.

처음에는 도착 구역을 기준으로 코드를 작성했다. 하지만 이렇게 짤 경우 문제가 있다.

A -> B, C -> B일 때, 각각 다른 경로임에도 불구하고 A -> B 에서 먼저 B를 방문했으므로 C -> B는 카운트하지 않는 것이다.

 

이때, 도착 구역이 아닌 방향의 필요성을 알게 되었다.

따라서 (출발점, 갈 방향)으로 map[x][y][dir]을 구성하고, 입력으로 들어온 커맨드를 적용하여 문제를 풀면 된다.

 

🔷 중복 경로는 무시한다.

map[x][y][dir]로 구현할 경우 중요한 점이 하나 있다.

바로 중복 경로는 무시한다는 것이다. 

이 말은 A -> B, B -> A 경로를 각각 따로 세지 않는다는 말을 의미한다.

중복 경로를 무시한 채 답을 구하려면, 로직 중간에 map[x][y][opposite dir]의 방문 여부도 true로 표시해 줘야 한다.

 

🔷 반대 방향 구하기

// 상 하 좌 우
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

int opposite = i ^ 1;

 

상(0), 하(1) /// 좌(2) 우(3)

이런 식으로 반대 방향이 숫자로 이어지게 dx, dy를 설정하면 ^(XOR) 연산으로 반대 방향을 손쉽게 구할 수 있다.

dir	dir ^ 1
0	1
1	0
2	3
3	2

 

하지만

좌(0) 상(1) 우(2) 하(3)

과 같은 경우는 XOR 연산이 통하지 않는다.

이럴 때에는 모듈러 연산을 통해 쉽게 반대 방향을 얻을 수 있다.

int opposite = (i + 2) % 4;

 

🔵 전체 코드

#include <string>
#include <iostream>

using namespace std;

// 상 하 좌 우
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
bool map[11][11][4];

int findIndex(char c)
{
    if (c == 'U') return 0;
    else if (c == 'D') return 1;
    else if (c == 'L') return 2;
    else return 3;
}

// (출발점, 갈 방향)을 기준으로 작성 
int solution(string dirs) {
    int answer = 0;
    pair<int, int> pos = { 5, 5 };

    for (char c : dirs)
    {
        int i = findIndex(c);
        int opposite = i ^ 1;
        int nx = pos.first + dx[i];
        int ny = pos.second + dy[i];

        if (nx < 0 || nx > 10 || ny < 0 || ny > 10) continue;
        if (map[pos.first][pos.second][i] == false && map[nx][ny][opposite] == false)
        {
            answer++;
            map[pos.first][pos.second][i] = true;
            map[nx][ny][opposite] = true;
        }

        pos = { nx, ny };
    }

    return answer;
}

 

🔵 시간 복잡도

for문에서 dirs의 길이만큼 순회하므로,  dirs의 길이가 N일 때 시간 복잡도는 O(N)이다.