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

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

프로그래머스

풀이

기본적으로 DFS를 써야한다는 걸 직감하긴 했으나 어떻게 구현할지 막막했다.

까다로운 부분은 크게 두 가지다.

1. 체크를 어떻게 할지?

2. 사이클을 어떻게 판단할지?

1번에 대해서는 방문 체크 배열을 3차원으로 놓고 해결하면 된다. 요새 DFS 문제에서 많이 사용하는 방식이다(점프, 텔레포트 등...).

사이클의 경우 같은 방향으로 같은 지점을 방문하면 사이클이라고 판단할 수 있다. 따라서, 사이클이 아니라면 방문 체크 배열의 3차원 축에 대해 중복 방문을 하지 않는다.

마지막으로 방문 지점이 'S'가 아닐 경우 방향을 바꿔주는 함수 changeDir 과, 범위를 벗어났을 때 nr, nc를 처리하여 DFS를 수행하면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M;
bool visited[510][510][4];
vector<string> map;
 
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };
 
int changeDir(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 dfs(int row, int col, int dir, int dist)
{
    if (visited[row][col][dir]) return dist;
    
    visited[row][col][dir]=true;
    
    int ndir=dir;
    if (map[row][col]!='S') ndir = changeDir(map[row][col], dir);
    int nr = row+dr[ndir];
    int nc = col+dc[ndir];
    
    if (nr<0) nr=N-1;
    if (nc<0) nc=M-1;
    if (nr==N) nr=0;
    if (nc==M) nc=0;
    
    return dfs(nr, nc, ndir, dist+1);
    
}
 
vector<int> solution(vector<string> grid)
{
    vector<int> answer;
    N = grid.size();
    M = grid[0].size();
    map = grid;
    
    for (int i=0; i<N; i++){
        for (int j=0; j<M; j++){
            for (int k=0; k<4; k++){
                int res = dfs(i, j, k, 0);
                if (res > 0){
                    answer.push_back(res);
                }
            }
        }
    }
    sort(answer.begin(), answer.end());
    return answer;
}