[백준 15685] 드래곤 커브(JAVA/C++)

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

15685번: 드래곤 커브

 

[JAVA]

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

class Dragon{
	int x;
	int y;
	int d;
	int g;
	public Dragon(int x, int y, int d, int g) {
		super();
		this.x = x;
		this.y = y;
		this.d = d;
		this.g = g;
	}
	
}
public class Main {

	static int N;
	static Dragon[] dragonCurve;
	static boolean[][] visit;
	static int[] dx= {0,-1,0,1};
	static int[] dy= {1,0,-1,0};
	//우상좌하
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N=Integer.parseInt(br.readLine());
		dragonCurve=new Dragon[N];
		visit=new boolean[101][101];
		for(int i=0; i<N; i++) {//x,y반대로 입력받기
			st=new StringTokenizer(br.readLine()," ");
			int x; int y; int d; int g;
			y=Integer.parseInt(st.nextToken());
			x=Integer.parseInt(st.nextToken());
			d=Integer.parseInt(st.nextToken());
			g=Integer.parseInt(st.nextToken());
			dragonCurve[i]=new Dragon(x,y,d,g);
		}
		for(int i=0; i<N; i++) {
			draw(dragonCurve[i]);
		}
		int ans=0;
		for(int i=0; i<=99; i++) {
			for(int j=0; j<=99; j++) {
				if(visit[i][j]==true && visit[i][j+1]==true
					&&visit[i+1][j]==true && visit[i+1][j+1]==true)
					ans++;
			}
		}
		System.out.println(ans);
		
	}


	private static void draw(Dragon dragon) {
		int x=dragon.x;	int y=dragon.y;
		int d=dragon.d; int g=dragon.g;
		visit[x][y]=true;
		int nx=x+dx[d];
		int ny=y+dy[d];
		visit[nx][ny]=true;
		if(g==0)return;
		Deque<Integer> dq=new ArrayDeque<Integer>();
		
		dq.add(d);
		x=nx; y=ny;
		while(g-->0) {
			Deque<Integer> tmp=new ArrayDeque<Integer>();
			tmp.addAll(dq);
			while(!dq.isEmpty()) {
				int nd=dq.pollLast();
				if(nd<3)nd++;
				else nd=0;
				nx=x+dx[nd];
				ny=y+dy[nd];
				visit[nx][ny]=true;
				tmp.offerLast(nd);
				x=nx; y=ny;
			}
			dq.addAll(tmp);
		}
	}
}

 

 

 

[C++]

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N;
//우 상 좌 하
int dx[4] = { 0,-1,0,1 };
int dy[4] = { 1,0,-1,0 };
//0->1, 1->2, 2->3, 3->0
bool visited[101][101] = { 0, };

struct dragon {
	int x, y, d, g;
};
vector <dragon> curve;

void Solve() {
	for (int i = 0; i < curve.size(); i++) {
		deque <int> dq, tmpQ;
		int x = curve[i].x; int y = curve[i].y;
		int d = curve[i].d; int g = curve[i].g;
		visited[x][y] = true;
		int nx = x + dx[d];
		int ny = y + dy[d];
		visited[nx][ny] = true;
		if (g == 0) continue;

		dq.push_back(d);
		x = nx; y = ny;
		while (g--) {
			
			tmpQ = dq;
			while (!dq.empty()) {

				int nd = dq.back();
				dq.pop_back();

				if (nd < 3) nd++;
				else nd = 0;
				nx = x + dx[nd];
				ny = y + dy[nd];
				visited[nx][ny] = true;
				tmpQ.push_back(nd);
				x = nx; y = ny;
			}
			while (!tmpQ.empty()) {
				int val = tmpQ.front();
				tmpQ.pop_front();
				dq.push_back(val);
			}
		}
			
	}
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x, y, d, g;
		cin >> x >> y >> d >> g;
		curve.push_back({ y,x,d,g });
	}
	Solve();
	int ans = 0;
	for (int i = 0; i <= 99; i++) {
		for (int j = 0; j <= 99; j++) {
			if (!visited[i][j] || !visited[i][j + 1]
				|| !visited[i + 1][j] || !visited[i + 1][j + 1])
				continue;
			ans++;
		}
	}
	cout << ans;
	return 0;
}