[프로그래머스(Programmers)][자바(java)] (Lv2) 빛의 경로 사이클 <월간코드챌린지3>

 

https://programmers.co.kr/learn/courses/30/lessons/86052

코딩테스트 연습 - 빛의 경로 사이클

 

문제 풀이

 

< 내가 푼 방법 >

 

import java.util.*;

public class Solution {

	public static int[] solution(String[] grid) {
		int r = grid.length, c = grid[0].length(), i, j, k; // row, column
		char g[][] = new char[r][c]; String ds; // grid, directions
		for (i = 0; i < r; ++i) {
			ds = grid[i];
			for (j = 0; j < c; ++j)
				g[i][j] = ds.charAt(j);
		}
		Set<String> path = new HashSet<>(); String p;
		List<Integer> len = new ArrayList<>();
		int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 }; // directional x/y
		int osx, osy, onx, ony, px, py, cx, cy, nx, ny, vx, vy, t, l; char d; 
		// original start/next x/y, previous x/y, current x/y, next x/y, value x/y,
		// tmp, len of the cycle, direction
		for (i = 0; i < r; ++i) {
			for (j = 0; j < c; ++j) {
				loop:
				for (k = 0; k < 4; ++k) {
					px = osx = i; py = osy = j;
					cx = onx = px + dx[k]; cy = ony =  py + dy[k];
					l = 0;
					while (true) {
						vx = cx - px; vy = cy - py;
						if (cx < 0)		{cx += r; px += r;}
						if (cy < 0)		{cy += c; py += c;}
						if (cx >= r)	{cx -= r; px -= r;}
						if (cy >= c) 	{cy -= c; py -= c;}
						l++;
						d = g[cx][cy];
						if (d == 'L' || d == 'R') {
							t = vx; vx = vy; vy = t;
							if (d == 'L' && Math.abs(vx) == 1) vx = -vx;
							if (d == 'R' && Math.abs(vy) == 1) vy = -vy;
						}
						nx = cx + vx; ny = cy + vy;
						p = px + "," + py + "/" + cx + "," + cy + "/" + nx + "," + ny;
						if (path.contains(p))
							continue loop;
						path.add(p);
						if (cx == osx && cy == osy)
							if (nx == onx && ny == ony)
								break;
						px = cx; py = cy;
						cx = nx; cy = ny;
					}
					len.add(l);
				}
			}
		}
		Collections.sort(len);
		int s = len.size();
		int ans[] = new int[s];
		for (i = 0; i < s; ++i)
			ans[i] = len.get(i);
		return ans;
	}
}

 

*  사이클은 출발 지점이나 출발 방향이 정해져 있지 않음

*  출발 지점을 각 칸으로 정하고, 동,서,남,북 방향으로 각각 경로를 구한 후 경로가 같으면 같은 사이클로 본다.
 ( 경로가 같다는 것은 이전->현재->다음 칸의 좌표가 모두 같은 것이 있을 때 )

*  입력받은 String[] grid 를 char[][] g 로 만든다. ( 행( r  ), 열( c  ) 개수도 구함 )

*  방향( S, L, R )에 따른 좌표 변화 구하기 ( 이전 칸( p  : prev ) -> 현재 칸( c  : curr ) -> 다음 칸( n  : next  ) )
 ( 이전 칸에서 현재 칸으로 이동 시 x, y 좌표에 각각 더한 값( vx, vy  )과 비교하여
   현재 칸에서 다음 칸으로 이동할 방향에 따라 x, y 좌표에 각각 더해야 하는 값 구하기 )
-  다음 이동 방향( 현재 칸에 써 있는 글자 )이
  -  ‘S'  =>  그대로
  -  ‘L'  =>  x, y 바꾼 후, |x|가 1이면 부호 변경
  -  ‘R'  =>  x, y 바꾼 후, |y|가 1이면 부호 변경

*  사이클, 사이클의 길이 구하기 ( 출발 방향이 동, 서, 남, 북일 때 각각에 대한 ) ( Set<String> path, List<Integer> len  )
-  격자 범위를 탐색 ( 0 <= i < r, 0 <= j < c )
-  출발 좌표( os : original start  )는 각 칸( i, j )으로 정함 ( 이 것이 최초의 ‘이전 칸( p )’이 됨 )
-  동, 서, 남, 북 각각으로 이동한 그 다음 좌표( on : original next  )도 구함 ( 이 것이 최초의 ‘현재 칸( c )’이 됨 )
 ( 출발 좌표로부터 동, 서, 남, 북으로 한 칸 이동한 좌표 )
-  현재 좌표( c )에서 이전 좌표( p )를 빼서 vx, vy를 구함
-  현재 좌표가 칸의 범위를 벗어날 시 ( 0 > x,y || x >= r || y >= c )
   좌표 값을 알맞게 더해줌 ( 이전 좌표도 같이 더해줌 )
  ┌  x 좌표가 벗어낫을 경우 x 좌표 += r
  └  y 좌표가 벗어낫을 경우 y 좌표 += c
-  사이클 길이 + 1하고 현재 좌표( c )에 쓰여진 다음 이동 방향( d ) 구하기 ( g[cx][cy] )
-  현재 좌표( c )에서 다음 좌표( n )로 이동할 때 더해야 할 값 vx, vy를 d에 따라 적절히 변경 
-  현재 좌표( c )에 쓰여진 d 방향으로 이동하여 다음 좌표( n )를 구함
-  경로를 저장하는 집합( path )에 이전좌표, 현재좌표, 다음좌표 값을 추가
 ( 이미 존재하면 같은 경로이므로 추가하지 않고 다음 루프로 넘어감 )
-  경로를 구하는 중 os( 출발 좌표 ) 로 돌아올 시, 그 다음 좌표가 on 이랑 같으면 한 사이클이다.
   각 사이클의 길이를 저장하는 리스트( len )에 길이 추가
-  이후, 현재 좌표( c )는 이전 좌표( p )가 되고 다음 좌표( n )는 현재 좌표( c )가 됨

*  len 리스트를 오름차순으로 정렬하고 int[] 배열에 차례로 값을 담아 리턴

 

 

< 해설에 나온 방법 >

 

https://prgms.tistory.com/101

import java.util.*;

public class Solution {
	
	int r, c, dx[] = { 0, 0, 1, -1 }, dy[] = { 1, -1, 0, 0 }; // directional x/y
	char g[][];
	
	public int[] move(int x, int y, int d) {
		x += dx[d]; y += dy[d];
		if (x < 0)	x += r;
		if (y < 0)	y += c;
		if (x >= r)	x -= r;
		if (y >= c)	y -= c;
		return new int[] { x, y };
	}
	
	public int rotate(int x, int y, int d) {
		char nd = g[x][y];
		if (nd == 'S') return d;
		if (nd == 'L') {
			if (d == 0) return 3;
			if (d == 1) return 2;
			if (d == 2) return 0;
			if (d == 3) return 1;
		}
		if (nd == 'R') {
			if (d == 0) return 2;
			if (d == 1) return 3;
			if (d == 2) return 1;
			if (d == 3) return 0;
		}
		return -1;
	}

	public int[] solution(String[] grid) {
		r = grid.length; c = grid[0].length(); // row, column
		g = new char[r][c]; String ds;
		int i, j, k, x, y, d, l, xy[]; // direction, length
		for (i = 0; i < r; ++i) {
			ds = grid[i];
			for (j = 0; j < c; ++j)
				g[i][j] = ds.charAt(j);
		}
		boolean v[][][] = new boolean[r][c][4];
		List<Integer> len = new ArrayList<>();
		for (i = 0; i < r; ++i) {
			for (j = 0; j < c; ++j) {
				for (k = 0; k < 4; ++k) {
					if (!v[i][j][k]) {
						x = i; y = j; d = k; l = 0;
						while (!v[x][y][d]) {
							v[x][y][d] = true;
							xy = move( x, y, d ); x = xy[0]; y = xy[1];
							d = rotate( x, y, d );
							l++;
						}
						len.add(l);
					}
				}
			}
		}
		Collections.sort(len);
		int s = len.size();
		int ans[] = new int[s];
		for (i = 0; i < s; ++i)
			ans[i] = len.get(i);
		return ans;
	}
}