[ 프로그래머스 [ 월간코드챌린지 ] 빛의 경로 사이클 ] (C++)

프로그래머스의 빛의 경로 사이클(월간 코드 챌린지) 문제이다.

 

[ 문제풀이 ]

맵이 주어졌을 때, 만들어 질 수 있는 모든 사이클에 대한 그 길이를 구해서 출력을 해야 하는 문제이다.

전체적인 접근 과정과 사이클을 판단하는 과정, 정답을 도출하는 과정까지 순차적으로 진행해보자.

 

#1. 접근 방법

먼저, 이 문제를 어떻게 접근할지에 대해서 부터 이야기를 해보자.

본인은 이 문제를 '완전탐색' 방식으로 접근해 보았다. 이 문제에서 완전탐색이라는 것은 어떤 부분을 다 탐색을 한다는 것일까 ??

바로, "시작점과 시작 방향에 대한 완전탐색" 을 의미한다.

이 문제에서 보면, 주어진 맵이 어떤 형태로 주어지고 맵의 각각의 값들(S, L, R)이 어떤 값을 의미하는지도 모두 나와있지만 가장 처음에 빛을 발사시키는 것에 대한 조건은 주어지지 않았다.

즉 ! 빛을 쏠 수 있는 모든 경우에 대해서 다 빛을 쏴보고 그 과정에서 발생하는 사이클을 판단할 것이다.

그리고 ! 지금부터 '좌표' 라는 말을 자주 사용할 것인데, 간단하게 이 문제에서 주어진 맵을 2차원 배열처럼 표현했을 때 나오는 좌표와 똑같이 생각을 하면 된다. 이 문제에서는 vector와 string형으로 맵이 주어졌지만, 이 또한 결국에는 '좌표'처럼 표현이 가능하다.

그럼, 모든 좌표와 모든 진행방향에 대해서 탐색을 하는 부분을 코드로 확인해보자.

    N = grid.size();
    M = grid[0].length();
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0 ; j < M; j++)
        {
            for(int k = 0 ; k < 4; k++)
            {
                int Result = Simulation(i, j, k, 0);
            }
        }
    }

위와 같이 표현이 가능하다. 모든 좌표와 모든 진행방향에 대해서 탐색을 진행해 보는 것이다.

위의 코드에서 'Simulation' 함수는 밑에서 이야기 하겠지만, 실제로 빛을 쏴보고 빛의 움직임을 표현하기 위해서 구현해 놓은 함수이다.

 

#2. 사이클 판단

두 번째로 이 문제에서 가장 핵심적인 부분인 사이클을 판단하는 부분에 대해서 이야기를 해보자.

"사이클이 생성되었다" 라는 것은 어떻게 표현을 할 수 있을까 ??? 사이클 이라는 것은 결국에는 이미 기존에 한번 진행했던 코스를 또 다시 재 방문 하게 된다면 생기게 될 것이다. 왜냐하면, 똑같은 코스를 계속해서 방문을 하게 될 것이기 때문이다.

그럼, 간단하게 "이미 방문을 했던 좌표에 재방문 하는 경우" 를 사이클이 생성되었다고 표현할 수 있을까 ?? 그렇지 않다.

단순히, 이미 방문했던 좌표를 재 방문한다는 이유로 사이클이 생성되었다고 표현을 할 수는 없다. 한 가지가 더 추가되어야 한다.

바로 "방향"이다. "이미 방문했던 좌표를 이미 방문했던 방향으로 재 방문하게 된다면 ?" 이는 사이클이 생성되었다고 볼 수 있다.

왜냐하면 이미 방문했던 좌표에 똑같은 방향으로 방문을 하게 된다면, 그 다음 루트 또한 기존에 방문한 루트를 방문하게 될 것이고 똑같은 루트가 반복된다는 것을 의미하기 때문이다.

그래서 본인은, "이미 방문했던 좌표를 같은 방향으로 방문한 적이 있는지" 를 나타내기 위해서 3차원 Visit배열을 하나 만들어 주었다.

Visit[A][B][C] = true 의 의미는 "(A , B)에 진행방향 'C'로 방문한 적이 있습니다" 를 의미한다.

그럼, 매 탐색 과정에 있어서 이 Visit배열을 어떻게 관리해야 하는지 예시를 통해서 이야기 해보자.

 

그렇다면 아래의 경우를 한번 살펴보자.

위와 같이 맵이 주어졌고, 여기서 위에서 빨강색 화살표로 표현되어 있는 진행방향으로 빛을 발사했다고 가정해보자.

그럼 아래 그림과 같은  루트로 빛이 움직이게 될 것이고, 사이클이 발생하게 될 것이다.

위와 같은 사이클이 발생하게 될 것이다. 그럼, "사이클의 길이가 '4'입니다" 라는 것을 정답에 추가시켜놓고, 탐색을 이어나갔다고 가정해보자. #1에서 이야기했듯이, 모든 좌표에서 모든 진행방향으로 탐색을 할 것이기 떄문에 아마 아래 그림과 같이 탐색을 시작하는 경우도 존재할 것이다. 그리고 탐색을 할 때마다, Visit배열을 초기화 시켰다고 가정해보자.

이 위에서 했던 경우는 (0 , 0)에 있는 'L'에서 아랫방향으로 빛을 쏜 경우에 대해서 탐색을 했다면, 이번에는 (1 , 0)에 있는 'L'에서 오른쪽 방향을 빛을 쏜 경우에 대해서 탐색을 해볼 것이다. 위에서 했던 경우에서는 이미 탐색을 해본 경로이지만, Visit배열을 초기화를 시켰기 때문에 이미 탐색을 해본 경로라고 판단하지 않을 것이고, 탐색을 진행하게 될 것이다.

그럼, 탐색을 쭉 진행하다보면 아마 아래의 그림과 같은 사이클이 발생하게 될 것이다.

어디서 많이 본 듯한, 사이클이 또 발생되었다. 바로, 이 위에서 진행했던 사이클이 또 다시 중복되어서 발생하게 된 것이다.

그런데, 이는 위에서 한번 탐색을 했던 사이클이기 때문에 '새로운 사이클이 발생했다' 라고 표현을 할 수가 없다.

이러한 상황이 발생한 이유는 아마도 'Visit배열을 초기화를 시켜 버렸기 때문'일 것이다.

그럼, Visit배열을 초기화 시키지 않았다고 가정을 해보고 다시 탐색을 해보자.

이렇게 빛을 쏘려고 봤더니, "(1 , 0)에서 오른쪽을 빛을 발사하는 경우는 이미 탐색을 한 적이 있습니다" 라고 Visit배열에 표현이 되어 있을 것이다. 바로 (0 , 0)에서 아래쪽으로 빛을 발사했을 때, 이미 탐색을 했기 때문이다.

그럼 ? 이미 탐색한 좌표를 같은 방향으로 똑같이 탐색을 했기 때문에, 또 다른 사이클이 발생을 했다고 판단하게 될 것이다.

왜냐하면 ! 우리가 지금까지 이야기한 바로, "사이클을 판단하는 방법은, 같은 좌표를 같은 진행방향으로 재방문 한 경우" 이기 때문이다. 우리가 이야기한 내용에 따르면, 이 경우가 사이클로 성립이 안될 이유가 없다.

Visit배열을 매 탐색시마다 초기화를 시켜도 문제가 되고, 시키지 않아도 문제가 되는 경우가 발생하게 된다.

그래서 본인은 Visit를 초기화 시키지 않되, "사이클의 길이가 0이라면 이는 중복된 사이클을 의미한다" 라고 판단해 주었다.

위의 그림과 같이 이미 한번 탐색한 사이클을 또 탐색을 하게 된다면, 결국 Visit배열에 의해서 길이가 0인 사이클이 나오게 될 것이다.

그래서, 사이클의 길이를 통해서 이를 해결해 주었다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M;
bool Visit[510][510][4];
vector<string> MAP;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
 
int Change_Dir(char C, int Dir)
{
    if (C == 'L')
    {
        if (Dir == 0) return 3;
        if (Dir == 1) return 2;
        if (Dir == 2) return 0;
        if (Dir == 3) return 1;
    }
 
    if (Dir == 0) return 2;
    if (Dir == 1) return 3;
    if (Dir == 2) return 1;
    if (Dir == 3) return 0;
}
 
int Simulation(int x, int y, int Dir, int Len)
{
    if (Visit[x][y][Dir] == true) return Len;
 
    Visit[x][y][Dir] = true;
 
    int nx = x;
    int ny = y;
    int nd = Dir;
 
    if (MAP[x][y] != 'S') nd = Change_Dir(MAP[x][y], Dir);
    nx = x + dx[nd];
    ny = y + dy[nd];
    if (nx < 0) nx = N - 1;
    if (ny < 0) ny = M - 1;
    if (nx == N) nx = 0;
    if (ny == M) ny = 0;
 
    return Simulation(nx, ny, nd, Len + 1);
}
 
vector<int> solution(vector<string> grid)
{
    vector<int> answer;
    N = grid.size();
    M = grid[0].length();
    MAP = grid;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            for (int k = 0; k < 4; k++)
            {
                int Result = Simulation(i, j, k, 0);
                if (Result != 0) answer.push_back(Result);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}