코딩테스트
[프로그래머스][C++] 빛의 경로 사이클
이쿠우우
2022. 3. 21. 21:46
반응형
https://programmers.co.kr/learn/courses/30/lessons/86052
코딩테스트 연습 - 빛의 경로 사이클
각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진
programmers.co.kr
글쓴이의 답
개인적인 풀이 임으로
이것보다 더 좋은 알고리즘은 많음...
이렇게도 풀이하는구나.. 공유하기 위해 올림...
이건 정말.. 내가 봐도 좀 무식하게 풀이한 것 같음
풀이 시간이 엄청 오래걸렸지만
최대한 답을 확인하지 않고 내 머리로 풀기위해 노력해본 문제임.
코드가 더러워도 이해부탁함..
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 500
// [MAX][MAX][0]
// 0 : 빈곳
// 1 : S
// 2 : L
// 3 : R
// 10 : 경로
// [MAX][MAX][1], [MAX][MAX][2]
// [MAX][MAX][0] 인 경우 사용
// 0 : 지나가지 않음
// 1 : 지나감
int map[MAX*3+1][MAX*3+1][3] = {0, };
// 상, 하, 좌, 우
int moveH[4] = {-1, 1, 0, 0};
int moveW[4] = {0, 0, -1, 1};
int hSize=0;
int wSize=0;
int makeMap(int wSize, int hSize, vector<string> &grid){
int gridW =0;
int gridH =0;
for(int i=0; i < hSize; i++){
for(int k=0; k < wSize; k++){
if(0 == i % 2){
if(1 == k % 2){
map[i][k][0] = 10;
}
}
else{
if(0 == k % 2){
map[i][k][0] = 10;
}
else{
char temp = grid[gridH][gridW];
if('S' == temp){
map[i][k][0] = 1;
}
else if('L' == temp){
map[i][k][0] = 2;
}
else if('R' == temp){
map[i][k][0] = 3;
}
gridW++;
}
}
}
if(1 == i % 2){
gridH++;
gridW=0;
}
}
return 0;
}
int checkInsertDirection(int locationH, int locationW, int prevH, int prevW){
int direction =0;
int checkH = locationH - prevH; // 1 = 위에서 아래, -1 = 아래서 위로 ,0 = 가로 확인
int checkW = locationW - prevW; // 1 = 왼쪽에서 오른쪽, -1 = 오른쪽에서 왼쪽 ,0 = 세로 확인
if (1 < checkH) {
checkH = -1;
}
if (-1 > checkH) {
checkH = 1;
}
if (1 < checkW) {
checkW = -1;
}
if (-1 > checkW) {
checkW = 1;
}
// 위에서 아래로 들어옴,
if(1 == checkH){
direction =1;
}
// 오른쪽에서 왼쪽으로 들어옴,
else if(-1 == checkW){
direction =2;
}
// 아래에서 위로 들어옴
else if(-1 == checkH){
direction =3;
}
// 왼쪽에서 오른쪽으로 들어옴
else if(1 == checkW){
direction =4;
}
return direction;
}
int cycle(int direction, int locationH, int locationW, int prevH, int prevW){
int count = 0;
while(map[locationH][locationW][direction] != 1){
// 이동 경로인 경우
if(10 == map[locationH][locationW][0]){
map[locationH][locationW][direction] = 1;
count++;
int check = checkInsertDirection(locationH, locationW, prevH, prevW);
int nextH = 0;
int nextW = 0;
if (1 == check) {
nextH = locationH + 1;
nextW = locationW;
direction = 2;
}
else if (2 == check) {
nextH = locationH;
nextW = locationW - 1;
direction = 1;
}
else if (3 == check) {
nextH = locationH - 1;
nextW = locationW;
direction = 1;
}
else if (4 == check) {
nextH = locationH;
nextW = locationW + 1;
direction = 2;
}
if (nextH < 0) {
nextH = hSize - 1;
count--;
}
else if (nextH == hSize) {
nextH = 0;
count--;
}
if (nextW < 0) {
nextW = wSize - 1;
count--;
}
else if (nextW == wSize) {
nextW = 0;
count--;
}
prevH = locationH;
prevW = locationW;
locationH = nextH;
locationW = nextW;
}
// S인 경우
else if(1 == map[locationH][locationW][0]){
int check = checkInsertDirection(locationH, locationW, prevH, prevW);
int nextH =0;
int nextW =0;
if(1 == check){
nextH = locationH+1;
nextW = locationW;
direction = 2;
}
else if(2 == check){
nextH = locationH;
nextW = locationW - 1;
direction = 1;
}
else if(3 == check){
nextH = locationH-1;
nextW = locationW;
direction = 1;
}
else if(4 == check){
nextH = locationH;
nextW = locationW + 1;
direction = 2;
}
if(nextH < 0){
nextH = hSize-1;
}
else if(nextH == hSize){
nextH = 0;
}
if(nextW < 0){
nextW = wSize-1;
}
else if(nextW == wSize){
nextW = 0;
}
prevH = locationH;
prevW = locationW;
locationH = nextH;
locationW = nextW;
}
// L인 경우
else if(2 == map[locationH][locationW][0]){
int check = checkInsertDirection(locationH, locationW, prevH, prevW);
int nextH =0;
int nextW =0;
if(1 == check){
nextH = locationH;
nextW = locationW+1;
direction = 2;
}
else if(2 == check){
nextH = locationH+1;
nextW = locationW;
direction = 2;
}
else if(3 == check){
nextH = locationH;
nextW = locationW-1;
direction = 1;
}
else if(4 == check){
nextH = locationH-1;
nextW = locationW;
direction = 1;
}
if(nextH < 0){
nextH = hSize-1;
}
else if(nextH == hSize){
nextH = 0;
}
if(nextW < 0){
nextW = wSize-1;
}
else if(nextW == wSize){
nextW = 0;
}
prevH = locationH;
prevW = locationW;
locationH = nextH;
locationW = nextW;
}
// R인 경우
else if(3 == map[locationH][locationW][0]){
int check = checkInsertDirection(locationH, locationW, prevH, prevW);
int nextH =0;
int nextW =0;
if(1 == check){
nextH = locationH;
nextW = locationW-1;
direction = 1;
}
else if(2 == check){
nextH = locationH-1;
nextW = locationW;
direction = 1;
}
else if(3 == check){
nextH = locationH;
nextW = locationW+1;
direction = 2;
}
else if(4 == check){
nextH = locationH+1;
nextW = locationW;
direction = 2;
}
if(nextH < 0){
nextH = hSize-1;
}
else if(nextH == hSize){
nextH = 0;
}
if(nextW < 0){
nextW = wSize-1;
}
else if(nextW == wSize){
nextW = 0;
}
prevH = locationH;
prevW = locationW;
locationH = nextH;
locationW = nextW;
}
}
return count;
}
vector<int> solution(vector<string> grid) {
vector<int> answer;
hSize = (int)grid.size() *2 +1;
wSize = (int)grid[0].size()*2 +1;
makeMap(wSize, hSize, grid);
for(int i=1; i < hSize; i+=2){
for(int k=1; k < wSize; k+=2){
for(int n =0; n < 4; n++){
int goH = i + moveH[n];
int goW = k + moveW[n];
int direc = n %2 + 1; // 1 =상,좌, , 2=하,우
if(1 == map[goH][goW][direc]){
continue;
}
int count = cycle(direc, goH, goW, i, k);
answer.push_back(count);
}
}
}
sort(answer.begin(), answer.end());
return answer;
}
꾸준히 하다보면 실력이 늘겠지..
반응형