문제 URL : https://programmers.co.kr/learn/courses/30/lessons/86052
코딩테스트 연습 - 빛의 경로 사이클
각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진
programmers.co.kr
해당 가질수있는 방향은 총4가지입니다.
어느지점에서 출발하든 반드시 사이클이 존재하기때문에 방향에따라 visit를 주어서 그방향에 따른 visit에 다시밟게된다면 그곳은 싸이클입니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
//By 콩순이내장고
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define vi v<int>
#define vvi v<vi>
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
char alpha[255] = {};
int n, m;
vvi check[4];
int dfs(int y, int x, int dir,vector<string>&grid) {
if (check[dir][y][x]) {
return 0;
}
check[dir][y][x] = 1;
dir = (4 + (dir + alpha[grid[y][x]])) % 4;
int ny = (n + y + dy[dir]) % n;
int nx = (m + x + dx[dir]) % m;
return 1+dfs(ny, nx, dir, grid);
}
vector<int> solution(vector<string> grid) {
vector<int> answer;
n = grid.size();
m = grid[0].size();
alpha['L'] = -1;
alpha['R'] = 1;
check[0] = check[1] = check[2] = check[3] = vvi(n, vi(m));
for(int i=0;i<n;i++){
for (int j = 0; j < m; j++) {
for (int k = 0; k < 4; k++) {
if (!check[k][i][j])
answer.push_back(dfs(i, j, k, grid));
}
}
}
sort(answer.begin(), answer.end());
return answer;
}
|
cs |
궁금한점 혹은 모르는점 논리적인 오류등 어떤 질문이든 댓글은 언제나 환영입니다.
'프로그래머스' 카테고리의 다른 글
| 프로그래머스 입양 시각 구하기(2) (0) | 2022.03.29 |
|---|---|
| 프로그래머스 110 옮기기(월간 코드 챌린지 시즌2) (0) | 2022.03.25 |
| 프로그래머스 단속카메라 (0) | 2021.11.02 |
| 프로그래머스 디스크 컨트롤러 (0) | 2021.11.02 |
| 프로그래머스 n^2 배열 자르기 (0) | 2021.11.02 |
