[백준 - 15685] 골드4 - 드래곤 커브

1. 유형

그리디, 시뮬레이션

 

2. 풀이법

 

예를 들어서 0 1 2 1 방향으로 움직일 때,

 

다음 세대의 방향은 전 방향(0 1 2 1) + (2 3 2 1)가 된다

 

2 3 2 1 구하는 방법은 0 1 2 1의 끝부터 반대방향-1을 해주면 된다

 

1 -> 3(반대방향) -> 2(-1을 해줌)

2 -> 0(반대방향) -> 3(-1을 해줌, -1은 3으로 치환)

 

이런 식으로 시뮬레이션을 돌린다.

 

아래는 이와 관련된 코드이다

 

그런 다음 visit 배열에 방문 처리를 한다음 4개의 꼭지점이 true인 것의 갯수를 세주면 된다.

 

3. 코드

 

package 삼성역태;

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

public class Beak_15685드래곤커브 {
	static boolean visit[][];
	static int dr[] = {0,-1,0,1};
	static int dc[] = {1,0,-1,0};
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		int N = Integer.valueOf(st.nextToken());
		visit = new boolean[101][101];
		for(int i=0; i<N;i ++) {
			st = new StringTokenizer(in.readLine(), " ");	
			int c=Integer.valueOf(st.nextToken());
			int r=Integer.valueOf(st.nextToken());
			int d=Integer.valueOf(st.nextToken());
			int g=Integer.valueOf(st.nextToken());
			visit[r][c]=true;
			ArrayList<Integer> list = new ArrayList<>();
			list.add(d);
			for(int j=1; j<=g; j++) {
				for(int k=list.size()-1; k>=0; k--) {
					int nd = (list.get(k)+2)%4;
					nd-=1;
					nd = nd==-1 ? 3:nd;
					list.add(nd);
				}
			}
			move(r,c,list);
		}
		int ans = check();
		System.out.println(ans);
	}
	static void move(int r, int c, ArrayList<Integer> list) {
		for(int k : list) {
			r = r+dr[k];
			c = c+dc[k];
			visit[r][c] = true;
		}
	}
	static int check() {
		int ans=0;
		for(int i=0; i<101; i++) {
			for(int j=0; j<101; j++) {
				if(i+1>100 || j+1>100) continue;
				if(visit[i][j] && visit[i+1][j+1] && 
						visit[i+1][j] && visit[i][j+1]) {
					ans++;
				}
			}
		}
		return ans;
	}
}