BOJ - 드래곤 커브 15685번 (JAVA)

❓ 문제 - 백준 드래곤 커브 15685번 - JAVA 풀이법

출처 

(https://www.acmicpc.net/problem/15685)

15685번: 드래곤 커브

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

 

- 구현 핵심 아이디어는 다음과 같다.

• 방향 동(0), 북(1), 서(2), 남(3) 으로 잡았을 때 (현재 방향 인덱스 + 1) % 4 한 값은 문제에서 주어진 방향을 90도로 회전한 값이다.
• 리스트에서 그 전 세대들의 모든 방향을 마지막부터 꺼내와서 90도 회전시켜 이동한 후 다시 90도 회전한 방향들을 리스트에 넣어주면서 반복한다. 
• 0세대의 경우 동(0) 으로 움직였을 때 동(0) 방향을 리스트에 넣어준다.
• 1세대의 경우 리스트의 마지막 넣은 것부터 꺼내오면 동(0)이므로 이것을 90도 회전하면 북(1)이므로 해당 방향에 맞춰 이동한 후 list에 북(1) 방향을 넣어준다.
• 2세대의 경우 리스트의 마지막 넣은 것부터 꺼내오면 북(1)이고 이것을 90도 회전하면 서(2)이므로 서로 이동한 후, 또 리스트에서 동(0)을 꺼내와서 90도 회전시키면 북(1)이다. 해당 방향의 맞춰 이동 처리해주면 된다. 그리고 이동한 방향들을 리스트에 넣어준다.
•  3세대의 경우 리스트의 마지막 넣은 것부터 꺼내오면 북(1)이고 이것을 90도 회전하면 서(2), 그 다음 꺼내온 방향은 서(2)이고 이것의 90도 회전 은 남(3), 그 다음은 북(1)을 꺼내와서 이것을 90도 회전하면 서(2) 이다. 그 다음 동(0)을 꺼내와서 이것을 90도 회전하면 북(1) 이다. 90도 이동시켜 이동한 방향들을 다시 list에 넣어준다. 

 

 

2. 느낀점

• 처음 스택으로 할까 list로 할까 고민하다가 stack보다는 인덱스 접근이 편한 arrayList를 활용하였다.
• 처음에 이정도로 간결한 코드는 아니였지만 다른 사람들의 코드를 참고하며 줄일 것은 줄이고 좀 더 간결한 코드를 작성해보았다. 
• 이 문제는 아이디어 싸움인 것 같다.. 다음에도 이런 비슷한 문제를 만나면 빠르고 정확하게 풀어내야지 !

 

💻 소스코드

// BOJ - 드래곤 커브(15685번)
// 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_15685 {
	public static int[] dx = {0, -1, 0, 1};
	public static int[] dy = {1, 0, -1, 0};
	public static boolean[][] visited;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int n = Integer.parseInt(br.readLine());
		visited = new boolean[101][101];
		
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int g = Integer.parseInt(st.nextToken());
			visited[x][y] = true;
			ArrayList<Integer> dir_list = new ArrayList<>();
			dir_list.add(d);
			
			
			for(int p=1;p<=g;p++) {
				for(int q=dir_list.size()-1;q>=0;q--) {
					dir_list.add((dir_list.get(q)+1) % 4);
				}
				
			}
			for(int dir:dir_list) {
				x += dx[dir];
				y += dy[dir];
				visited[x][y] = true;
			}
			
		}
		
	
		
		int cnt = 0;
		for(int i=0;i<100;i++) {
			for(int j=0;j<100;j++) {
				if(visited[i][j] && visited[i+1][j] && visited[i][j+1] && visited[i+1][j+1]) {
					cnt++;
				
				}
					
			}
		}
		
		System.out.println(cnt);
	}

}