[프로그래머스] JetBrains x 프로그래머스 월간 코드 챌린지

본격적인 코테 치기전 몸풀기로 JetBrains x 프로그래머스를 지원해보았다. 

총 4문제중 2문제를 맞혔다. 3,4번은 문제 읽자마자 풀 수 없을 것같아서, 2번까지만 풀고 그냥 나왔다.

1번은 단순 구현이었기에 패스하고, 2번만 코드를 남겨본다!

 

2번문제는 주어진 맵에서 발생하는 모든 사이클의 대한 길이를 출력하는 문제였다. 각각의 경로마다 특징이 있었기에 DFS로 풀어야겠다고 생각했고, 동서남북 4가지 방향에 대한 방문 체크를 위해 3차원 DFS로 구현하였다.

 

분명 틀린게 없는게 자꾸 틀렸습니다가 뜨길래, 다시 문제를 읽어보니 출력시 오름차순 조건을 빼먹었었다. 이것때문에 거의 30분을 날려먹었다..... 허무하다

문제 조건을 꼼꼼히 확인하자 제발!!

 

전체 코드는 아래와같다.

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

char map[500][500];
int N, M;
int visit[500][500][4];
int dx[4] = { 0,1,0,-1 }; //동: 0 , 북:1, 서:2, 남:3 왼쪽으로 회전
int dy[4] = { 1,0,-1,0 };
int tmpCnt=0;
vector<int> answer;

void dfs(int x, int y,int dir) {
	if (visit[x][y][dir]) {
		answer.push_back(tmpCnt);
		return;
	}
	tmpCnt++;
	visit[x][y][dir] = 1;
	int nextX = x + dx[dir];
	int nextY = y + dy[dir];

	if (nextX == N) nextX = 0;
	else if (nextX == -1)nextX = N - 1;
	else if (nextY == M)nextY = 0;
	else if (nextY == -1) nextY = M - 1;
	
	if (map[nextX][nextY] == 'L') {
		dir++;
		if (dir == 4) dir = 0;
	}
	else if (map[nextX][nextY] == 'R') {
		dir--;
		if (dir == -1) dir = 3;
	}

	dfs(nextX, nextY, dir);
}

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