[programmers] 빛의 경로 사이클

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

프로그래머스

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

재귀

 

---------------------------------------------------풀이----------------------------------------------------

 

이 문제를 보자마자 생각난 것은 특정 격자 칸에서 어떤 방향으로 이동할지를 고려해야 한다는 점이다.

그 방향으로 이동했던 적이 있다면, 사이클이 생긴 것이다.

따라서, 이를 저장하기 위한 자료구조로 bool visited[x좌표][y좌표][이동할방향]를 사용하였다.

 

main이 되는 solution()함수는 다음과 같다.

모든 격자 칸에 대해, 네 방향(상하좌우)에서 빛이 들어왔을 경우를 생각하면 모든 케이스를 고려할 수 있다.

따라서, 모든 (x,y)에 대해, 그리고 각각에서 네 방향 dir에 대해,

go_light(x,y,dir)을 호출해 빛을 쏘고 리턴 값으로 그 때의 빛의 길이를 받았다.

만약 이 값이 0이면 사이클이 생기지 않았거나 이미 계산한 사이클이므로 저장하지 않는다.

마지막으로, answer에 저장된 사이클 길이들을 오름차순으로 정리해 리턴한다.

 

go_light(int x, int y, int dir) 함수는

(x,y)로 dir 방향에서 빛이 들어왔을 때 빛의 경로 길이를 리턴하는 함수이다.

dir은 상,우,하,좌(시계방향)의 순서대로 0,1,2,3을 의미한다.

우선, 들어온 빛이 (x,y) 격자를 지난 경우 바뀌는 방향을 계산해 dir을 갱신한다.

그 방향으로 이미 빛이 나간 적이 있으면(visited[x][y][dir] == true), 사이클이 생긴 것이므로 더 이상 방문하지 않고 0을 리턴한다.

아니라면, 방문한 것으로 처리(visited[x][y][dir] = true)하고 다음 위치로 이동한 경우를 계산한다.

즉, 현재 이동할 경로 길이(1) + 다음 위치로 이동한 경우의 계산 값(go_light(next_x, next_y, dir))을 리턴한다.

 

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

using namespace std;

vector<string> grid;
// 상, 우, 하, 좌
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
// visited[x좌표][y좌표][이동방향]
bool visited[501][501][4] = {false, };

void init_visited(){
    memset(visited, sizeof(visited), false);
}

// 격자의 글자에 따라 방향 수정해 리턴
int change_dir(int x, int y, int dir){
    switch(grid[x][y]){
        case 'S':
            break;
        case 'L':
            dir--;
            if(dir < 0){
                dir = 3;
            }
            break;
        case 'R':
            dir = (++dir)%4;
            break;
    }
    return dir;
}

int calc_next_x(int x, int dir){
    x += dx[dir];
    if(x < 0){
        x = grid.size()-1;
    }
    return x % grid.size();
}

int calc_next_y(int y, int dir){
    y += dy[dir];
    if(y < 0){
        y = grid[0].length()-1;
    }
    return y % grid[0].length();
}

// 이동한 위치 (x,y)와 빛이 들어온 방향 dir.
int go_light(int x, int y, int dir){
    // 빛이 격자에 도달할 경우 이동해야 할(꺾일) 방향으로 dir 수정
    dir = change_dir(x, y, dir);
    // 이미 방문한 방향이면, 그 방향으로 이동하지 않고 종료.
    if(visited[x][y][dir]){
        return 0;
    }
    visited[x][y][dir] = true;
    // 다음 격자 위치로 이동했을 때의 길이를 더해 리턴.
    return 1 + go_light(calc_next_x(x, dir), calc_next_y(y, dir), dir);
}

vector<int> solution(vector<string> _grid) {
    vector<int> answer;
    grid = _grid;
    // 모든 좌표에 대해
    for(int i = 0; i < grid.size(); i++){
        for(int j = 0; j < grid[0].length(); j++){
            // 각 네 방향으로 빛 쏘기
            for(int k = 0; k < 4; k++){
                // (i,j)부터 빛을 쏘고 사이클의 길이를 받아옴
                int tmp = go_light(i, j, k);
                // 길이가 0이면 사이클 생성x => 저장 안함.
                if(tmp == 0){
                    continue;
                }
                answer.push_back(tmp);
            }
        }
    }
    // answer를 오름차순으로 정렬
    sort(answer.begin(), answer.end());
    return answer;
}

 

---------------------------------------------------후기----------------------------------------------------

 

아이디어는 제대로 구상했고 문제가 없었지만, 예외를 생각지 못해 한 번 틀렸던 문제.

어떤 칸에서 시작해서 다른 칸을 모두 도는 것만이 사이클이 아니다.

그 부분을 생각지 못해 (0,0)에서 시작하는 경우만 생각해서 틀렸었다.

즉, 질문하기에 나와있는 예외 케이스를 보고 무엇이 문제인지 찾을 수 있었다.

S

S

위와 같은 격자가 주어질 때, 사이클은 총 6가지가 가능하다.

(0,0)에서 시작하면 좌, 우 방향으로 이동할 경우 (1,0)은 방문하지 않는 사이클이 생성되고,

(1,0)에서 시작하면 좌, 우 방향으로 이동할 경우 (0,0)은 방문하지 않는 사이클이 생성된다.

이 부분을 해결하자 정답 처리가 될 수 있었다.