[프로그래머스] 빛의 경로 사이클 (C++)

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

코딩테스트 연습 - 빛의 경로 사이클

level 2 구현 (배열)

우선 사이클에 대해서 이해가 잘 안돼서 블로그를 찾아보고 이해했다. (역시 국어문제인가)

사이클은 같은 노드, 같은 방향을 다시 만났을 때 사이클이 이루어진다.

 

접근방법

모든 노드에서 갈 수 있는 모든 방향으로 경로가 뻗어나간다.

이를 위해 3중 for문을 돌려 각 노드의 각 방향으로 출발하는 (이름만)dfs함수를 호출한다.

dfs함수는 일련의 재귀 호출을 반복한 후 사이클이 형성되면 경로의 길이를 반환한다.

사이클이 형성되지 않은 경우는 dfs함수가 0을 반환할 때이다. 사실 이 부분은 다른 블로그를 참고했는데, 완전히 와닿지는 않아서

경로의 중간부터 사이클이 형성되는 경우는 없다는 것 정도만 받아들이고 풀었다.

 

이름만 dfs인 함수를 사용했는데,

dfs함수는 현재 도착한 노드(r,c)와 현재 노드에 도달한 방향(dirR, dirC), 현재 경로의 길이(len)를 인자로 받는다.

현재 노드에 도착한 경로가 이미 방문된 적이 있으면 -> 당시 경로길이를 반환하여 재귀호출을 종료한다.

그렇지 않으면 현재 노드에 도착한 경로를 방문했다고 표시하고,

도착한 노드의 값에 따라(L, S, R) 다음 방향을 구한다. (changeDirection 함수 사용)

다음 방향을 토대로 다음 방문할 노드와 방향, 1 증가된 경로의 길이를 인자에 담아 dfs를 호출한다.

 

오답노트

음수 모듈로 연산에서 음수가 나온다는 걸 몰라서 core dump만 엄청 떴었다.

나누어지는 수가 음수일 경우 나누는 수를 더해줘야한다. 근데 음수가 아니어도 나누는 수를 더해줘도 된다. (어차피 더하는 수로 나눌거니까..똑같은 ㅇㅇ 먼지 알지)

그리고 방향을 바꾸는 함수를 구현할 때도 공식을 잘못써서 틀렸었다.

 

소스코드

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

using namespace std;

bool visit[501][501][4][4];
int dr[] = {0,0,1,-1};
int dc[] = {1,-1,0,0};
int w, h;
vector<string> map;

void changeDirection(char sign, int *dirR, int *dirC){
    if (sign == 'S')
        return;
    
    int oldDirR = *dirR;
    int oldDirC = *dirC;
    
    if((oldDirC == 0 && sign == 'L') || (oldDirR == 0 && sign == 'R')) {
        *dirR = oldDirC;
        *dirC = oldDirR;
    } else {
        *dirR = -oldDirC;
        *dirC = -oldDirR;        
    }
}

int dfs(int r, int c, int dirR, int dirC, int len){
    if (visit[r][c][dirR][dirC])
        return len;
    visit[r][c][dirR][dirC] = true;
    
    changeDirection(map[r][c], &dirR, &dirC);
    int nr = (r + dirR + h) % h;
    int nc = (c + dirC + w) % w;
    
    return dfs(nr,nc,dirR,dirC,len+1);
}

vector<int> solution(vector<string> grid) {
    vector<int> answer;
    h = grid.size();
    w = grid[0].length();
    map = grid;
    
    for(int r = 0 ; r < h ; r++){
        for(int c = 0 ; c < w ; c++){
            for(int d = 0 ; d < 4 ; d++){
                int len = dfs(r,c,dr[d],dc[d],0);
                if(len != 0)
                    answer.push_back(len);
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}