문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/86052
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
정답률이 왜 이렇게 낮나 했더니, 문제 이해하기가 난해했다.
진짜 친구랑 둘이서 푸는데, 문제 해석으로 토론할 줄은 몰랐지..
솔직히 깔끔한 문제는 아니었다고 생각했다.
문제 핵심 및 풀이
'빛의 경로 사이클'에 대한 정의
이 문제의 핵심이자 가장 애매했던 부분이다.
문제에서는 빛의 경로 사이클을 "빛이 이동하는 순환 경로를 의미"한다고 정의했다.
진짜 딱 이 한 문장이라 나머지는 예제를 통해서 우리가 알아서 해석해야 한다..
문제가 너무 불친절하다.
최종적으로 내린 빛의 경로 사이클에 대한 결론은
(처음 시작한 칸) + (처음 시작한 방향)으로 돌아올 수 있다면 사이클이 발생하는 것이다.
중복 사이클에 대한 검사
해당 문제를 해결하기 위해 무조건 판별해 내야 하는 것이다.
지금 진행하고 있는 빛의 경로가, 새로운 사이클인지를 어떻게 판별해 내야 할까?
이를 알아내기 위해, ["SL", "LR"] , ["R", "R"]를 비교 분석했다.
["SL", "LR"]은 사이클이 오직 하나만 발생하고,
["R", "R"]은 사이클이 2개가 발생한다.
어떤 것이 이러한 차이를 만드는 것일까?
S칸에서 아래 방향(↓)으로 출발했을 때의 사이클 경로이다.
그렇다면 S칸에서 왼쪽 방향(←)으로 출발한다면?
13번째 움직임을 처음으로 하는 것과 다름이 없기 때문에,
위 그림과 차이가 없다. 따라서 같은 사이클이 된다.
이 외에도 같은 칸의 다른 방향, 다른 칸의 같은 방향 등 어디에서 시작해도
모두 위 그림과 연관되어 있기 때문에 같은 사이클이 되는 것이다.
그렇다면 ["R", "R"]은 어떨까?
왼쪽 사이클에서 위에 있는 R칸에서
아래로 출발하는 그림을 보면, 관여하지 않는 방향이 존재한다.
그리고 오른쪽 사이클을 보면,
왼쪽 사이클과 전혀 다른 방향으로 움직이는 것을 볼 수 있다.
즉, 두 사이클이 다르기 위해서는 빛의 방향 중 단 하나라도 겹처서는 안 되는 것이다.
방향 판단 및 중복 사이클 판단을 위한 전략
중요한 것은 이를 알고리즘으로 표현해 내는 것이다.
나는 이를 효율적으로 표현해 내기 위해, 이런 식의 칸이 있다고 생각했다.
현재 빛이 존재하는 칸의 위치를 매번 확인해야 한다.
그리고 빛이 특정한 방향으로 나갈 때, 그 방향으로 나갈 수 있는지 확인한다.
그 방향으로 나갈 수 있다면 그 방향을 나간 후,
해당 칸의 그 방향은 더 이상 사용할 수 없도록 막아둔다.
만약 그 방향으로 나갈 수 없다면 2가지 중 하나를 의미한다.
1. 이미 이전에 검출된 중복된 사이클이다.
2. 처음 시작했던 위치로 돌아왔다.(새로운 사이클을 의미)
1번의 경우 실패를 의미하는 0을 반환하도록 하고,
2번의 경우 빛의 이동 횟수를 반환하도록 했다.
이를 모든 칸에 대해서 반복했다.
실수하기 쉬운 부분
한쪽 끝으로 갔다면, 다른 쪽 끝으로 나와야 하기 때문에
mod 연산을 통해 이를 잘 정리해줘야 한다.
index out of bound가 나오기 쉽다.
이 부분을 조심해서 풀어야 한다.
코드 구현
C++ 구현 코드
↓
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct Point {
int x, y;
Point(int x, int y) : x(x), y(y) {}
};
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, -1, 0, 1};
int map[500][500];
bool visited[501][501][4];
int width;
int height;
void init(vector<string> grid) {
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].length(); j++) {
map[i][j] = grid[i][j];
}
}
height = grid.size();
width = grid[0].length();
}
Point move(int x, int y, int dir) {
int nx = (x + dx[dir]) % height;
int ny = (y + dy[dir]) % width;
nx = (nx < 0) ? height + nx : nx;
ny = (ny < 0) ? width + ny : ny;
return Point(nx, ny);
}
int rotate(int dir, int x, int y) {
int nDir;
switch (map[x][y]) {
case 'L':
nDir = (dir + 1) % 4;
break;
case 'R':
nDir = (dir - 1) % 4;
break;
default:
nDir = (dir) % 4;
}
return (nDir < 0) ? nDir + 4 : nDir;
}
int shoot(int sx, int sy, int dir) {
int result = 0;
int x = sx;
int y = sy;
while (!visited[x][y][dir]) {
visited[x][y][dir] = true;
result++;
Point p = move(x, y, dir);
x = p.x;
y = p.y;
dir = rotate(dir, x, y);
}
if (sx == x && sy == y) return result;
else return 0;
}
vector<int> solution(vector<string> grid) {
vector<int> answer;
init(grid);
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].length(); j++) {
for (int k = 0; k < 4; k++) {
int result = shoot(i, j, k);
if (result != 0) answer.push_back(result);
}
}
}
sort(answer.begin(), answer.end());
return answer;
}Java 구현 코드
↓
import java.util.*;
class Solution {
public static int[] dx = {-1,0,1,0};
public static int[] dy = {0,-1,0,1};
public char[][] map;
public boolean[][][] visited;
public int width;
public int height;
public int[] solution(String[] grid) {
init(grid);
List<Integer> answer = new ArrayList<>();
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[i].length(); j++){
for(int k = 0; k < 4; k++){
int result = bfs(i,j,k);
if(result != 0) answer.add(result);
}
}
}
Collections.sort(answer);
return answer.stream().mapToInt(e -> e).toArray();
}
private void init(String[] grid){
char[][] map = new char[grid.length][];
for(int i = 0; i < grid.length; i++){
char[] arr = grid[i].toCharArray();
map[i] = arr;
}
this.map = map;
visited = new boolean[grid.length][grid[0].length()][4];
height = grid.length;
width = grid[0].length();
}
private int bfs(int sx, int sy,int dir){
if(visited[sx][sy][dir]) return 0;
int result = 1;
Queue<Point> q = new LinkedList<>();
visited[sx][sy][dir] = true;
q.add(move(sx,sy,dir));
while(!q.isEmpty()){
Point p = q.poll();
int nx = p.x;
int ny = p.y;
dir = rotate(dir,nx,ny);
if(!visited[nx][ny][dir]){
visited[nx][ny][dir] = true;
result++;
q.add(move(nx,ny,dir));
}
else if(nx == sx && ny == sy){
return result;
}
else return 0;
}
return 0;
}
private Point move(int x, int y,int dir){
int nx = (x + dx[dir]) % height;
int ny = (y + dy[dir]) % width;
nx = (nx < 0)? height + nx : nx;
ny = (ny < 0)? width + ny : ny;
return new Point(nx,ny);
}
private int rotate(int dir, int x, int y){
int nDir;
switch(map[x][y]){
case 'L':
nDir = (dir + 1)%4;
break;
case 'R':
nDir = (dir - 1)%4;
break;
default:
nDir = (dir)%4;
}
return (nDir < 0)? nDir + 4 : nDir;
}
public static class Point{
int x,y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
}2가지 풀이가 있다.
물론 둘 다 비슷한데, 첫 번째는 내가 처음에 풀었던 방식인 BFS이다.
굳이 BFS로 풀 필요는 없긴 한데, 그냥 처음에 막연히 이렇게 떠오르더라.
사실 두 번째가 더 편하고 깔끔하긴 하다.
import java.util.*;
class Solution {
public static int[] dx = {-1,0,1,0};
public static int[] dy = {0,-1,0,1};
public char[][] map;
public boolean[][][] visited;
public int width;
public int height;
public int[] solution(String[] grid) {
init(grid);
List<Integer> answer = new ArrayList<>();
for(int i = 0; i < grid.length; i++){
for(int j = 0; j < grid[i].length(); j++){
for(int k = 0; k < 4; k++){
int result = shoot(i,j,k);
if(result != 0) answer.add(result);
}
}
}
Collections.sort(answer);
return answer.stream().mapToInt(e -> e).toArray();
}
private void init(String[] grid){
char[][] map = new char[grid.length][];
for(int i = 0; i < grid.length; i++){
char[] arr = grid[i].toCharArray();
map[i] = arr;
}
this.map = map;
visited = new boolean[grid.length][grid[0].length()][4];
height = grid.length;
width = grid[0].length();
}
private int shoot(int sx, int sy, int dir){
int result = 0;
int x = sx;
int y = sy;
while(!visited[x][y][dir]){
visited[x][y][dir] = true;
result++;
Point p = move(x,y,dir);
x = p.x;
y = p.y;
dir = rotate(dir,x,y);
}
if(sx == x && sy == y) return result;
else return 0;
}
private Point move(int x, int y,int dir){
int nx = (x + dx[dir]) % height;
int ny = (y + dy[dir]) % width;
nx = (nx < 0)? height + nx : nx;
ny = (ny < 0)? width + ny : ny;
return new Point(nx,ny);
}
private int rotate(int dir, int x, int y){
int nDir;
switch(map[x][y]){
case 'L':
nDir = (dir + 1)%4;
break;
case 'R':
nDir = (dir - 1)%4;
break;
default:
nDir = (dir)%4;
}
return (nDir < 0)? nDir + 4 : nDir;
}
public static class Point{
int x,y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
}
시행착오
너무 오랜만에 풀어서 그런 것도 있고,
문제 이해가 어려워서 그런 것도 있고, 너무 오래 풀었다..
자괴감이 엄청 들고, switch 문에 break문을 깜빡해서 이런 식으로 곤욕을 겪을 줄이야..
알고리즘을 너무 오래 끊었다.
howudong님에게 보내주세요
토스아이디로 안전하게 익명 송금하세요.
toss.me