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

문제 링크

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

프로그래머스

 

풀이과정

# 해석

각 좌표마다 S L R 중 하나가 적혀있고, 그에 따라 빛이 움직이면서 처음 빛을 쐈던 위치로 돌아왔을 때의 이동 거리와

가능한 사이클의 개수를 구하는 문제입니다. 

 

- 위의 그림에서, 1번 방향으로 빛을 쏘기 시작했다면 결국 돌고 돌아서 16번을 이동한 다음 돌아오게 됩니다.

 

- 또한 빛이 이동하다가 끝에 도달했다면 반대쪽 끝으로 다시 돌아오게 됩니다.

- 입력 예시가 ["SL" , "L"] 이런식으로 나올 수는 없습니다.

빛이 이동해야 하기 때문에 가로 길이는 항상 동일하게 유지되어야 합니다.

 

 

 

# 풀이

1. 주어진 모든 좌표에 대해 탐색을 시작합니다.

방향은 상하좌우 4가지가 있기 때문에 모든 방향에 대해 DFS 탐색을 시작합니다.

 

vector<int> solution(vector<string> grid) {
    	N = grid.size();
	M = grid[0].size();
	arr = grid;
	for(int i=0; i<N; i++) {
		for(int j=0; j<M; j++) {
			for(int k=0; k<4; k++) {
				dfs(i,j,k,0);
			}
		}
	}
	sort(answer.begin(),answer.end());
    return answer;
}

 

2. 이미 방문했던 좌표라면 처음 지점으로 되돌아오는 것이기 때문에 지금까지 이동했던 거리를 return해줍니다.

단, 방향까지 동일해야 하기 때문에 visited[y][x][dir] 이런 형태로 정의를 해줘야 합니다.

void dfs(int y, int x, int dir, int cnt) {
	if(visited[y][x][dir] == true) {
		if(cnt != 0) answer.push_back(cnt);
		return;
	}
	visited[y][x][dir] = true;
	int ny,nx;
	int nD;

	if(arr[y][x] != 'S') nD = transform(arr[y][x],dir);
	ny = y + dy[nD];
	nx = x + dx[nD];

	if(ny >= N) ny = 0;
	if(nx >= M) nx = 0;
	if(ny < 0) ny = N-1;
	if(nx < 0) nx = M-1;

	dfs(ny,nx,nD,cnt+1);
}

 

방문하지 않았던 좌표라면 문자 'S' 'L' 'R' 에 따라 방향을 변경해주며 계속해서 재귀 탐색을 진행하면

답을 찾을 수 있습니다.

 

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// 상 하 좌 우
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
bool visited[500][500][4];
int N,M;
vector <string> arr;
vector<int> answer;

int transform(char c, int dir) {
	if(c == 'L') {
		if(dir == 0) return 2;
		if(dir == 1) return 3;
		if(dir == 2) return 1;
		if(dir == 3) return 0;
	}
	else if(c == 'R') {
		if(dir == 0) return 3;
		if(dir == 1) return 2;
		if(dir == 2) return 0;
		if(dir == 3) return 1;
	}
}

void dfs(int y, int x, int dir, int cnt) {
	if(visited[y][x][dir] == true) {
		if(cnt != 0) answer.push_back(cnt);
		return;
	}
	visited[y][x][dir] = true;
	int ny,nx;
	int nD;

	if(arr[y][x] != 'S') nD = transform(arr[y][x],dir);
	ny = y + dy[nD];
	nx = x + dx[nD];

	if(ny >= N) ny = 0;
	if(nx >= M) nx = 0;
	if(ny < 0) ny = N-1;
	if(nx < 0) nx = M-1;

	dfs(ny,nx,nD,cnt+1);
}

vector<int> solution(vector<string> grid) {
    N = grid.size();
	M = grid[0].size();
	arr = grid;
	for(int i=0; i<N; i++) {
		for(int j=0; j<M; j++) {
			for(int k=0; k<4; k++) {
				dfs(i,j,k,0);
			}
		}
	}
	sort(answer.begin(),answer.end());
    return answer;
}