-
[프로그래머스] 빛의 경로 사이클 c++Coding Test/programmers 2022. 10. 4. 11:44728x90
문제 설명
S, L , R 방향이 주어진다.
S는 직진, L 은 좌회전, R은 우회전 한다. (빛이 들어온 방향 기준)
기존에 방문한 좌표를 같은 방향으로 재방문한 경우 "싸이클"이 형성된다.
※사이클 : 같은 좌표, 같은 방향 으로 재방문
- 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다.
사이클을 찾고, 각 사이클의 길이를 구하는 문제이다.
제한 사항
- 1 ≤ grid의 길이 ≤ 500
- 1 ≤ grid의 각 문자열의 길이 ≤ 500
- grid의 모든 문자열의 길이는 서로 같습니다.
- grid의 모든 문자열은 'L', 'R', 'S'로 이루어져 있습니다.
입출력 예
grid result ["SL","LR"] [16] ["S"] [1,1,1,1] ["R","R"] [4,4] 풀이
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int N, M; bool Visit[510][510][4]; //(A, B)에 진행방향 C로 방문한 적이 있습니다. vector<string> MAP; // 0 , 1 , 2 , 3 //위, 아래, 오, 왼 int dx[] = { 0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; int Chanage_Dir(char C, int Dir){ // 0 : dx, dy index 번호 기준으로 봤을 때 // 2 3 // 1 if(C == 'L'){ if(Dir == 0){ //0의 왼쪽은 3 return 3; } if(Dir == 1){ //1의 왼쪽은 2 return 2; } if(Dir == 2){ //2의 왼쪽은 0 return 0; } if(Dir == 3){ //3의 왼쪽은 1 return 1; } } if(Dir == 0){ //0의 오른쪽은 2 return 2; } if(Dir == 1){ //1의 오른쪽은 3 return 3; } if(Dir == 2){ //2의 오른쪽은 1 return 1; } if(Dir == 3){ //3의 오른쪽은 0 return 0; } 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 = Chanage_Dir(MAP[x][y], Dir); } nx = x + dx[nd]; ny = y + dy[nd]; //순환할 수 있도록 좌표를 변경해준다. if(nx < 0){ nx = N -1; //0보다 작으면 max 좌표로 이동 } if(ny < 0){ ny = M -1; } if(nx == N){ //max 이면 0 좌표로 이동 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++){ //grid[i][] for(int j = 0; j < M; j++){ //grid[i][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; }
다른 풀이
bool is_visit[500][500][4]; vector<int> solution(vector<string> grid) { int dir[4][2] = {{0,1}, {-1,0}, {0,-1}, {1,0}}; vector<int> answer; for (int i=0; i<4; i++) for (int j=0; j<grid.size(); j++) for (int k=0; k<grid[0].size(); k++) if (is_visit[j][k][i] == false) { int r=j, c=k, d=i, l=1; is_visit[j][k][i] = true; while(1) { if (grid[r][c]== 'L') d = (d+1)%4; else if (grid[r][c] == 'R') d = (4+d-1)%4; r = (grid.size() + r + dir[d][0])%grid.size(); c = (grid[0].size() + c + dir[d][1])%grid[0].size(); if (is_visit[r][c][d]) break; is_visit[r][c][d] = true; l++; } answer.push_back(l); } sort(answer.begin(), answer.end()); return answer; }
728x90'Coding Test > programmers' 카테고리의 다른 글
[프로그래머스] 모음사전 c++ (0) 2022.10.11 [프로그래머스] 할인 행사 c++ (2) 2022.10.11 [프로그래머스] 전력망을 둘로 나누기 c++ (1) 2022.09.30 [프로그래머스] n^2 배열 자르기 c++ (0) 2022.09.29 [프로그래머스] 교점에 별 만들기 c++ (2) 2022.09.29