[구름톤 챌린지] Day 18 중첩 점 (Java)

구름LEVEL

 

문제 설명

한 변의 길이가 N인 정사각형이 있다.

플레이어는 정사각형 위에 M개의 반직선을 그린 뒤, 두 반직선이 교차하는 점의 수를 세려고 한다.

반직선을 그리는 과정은 아래와 같습니다.

 

1. 반직선을 그리기 시작할 칸 (y, x)를 정한다. (y, x)는 y행 x열을 의미합니다.

2. 반직선을 그릴 방향 d를 정한다. 방향은 상하좌우 중 하나이며, 항상 정사각형 테두리와 평행합니다.

3. 반직선을 그린다. 반직선은 항상 시작칸의 테두리부터 시작하며, 같은 칸을 지나는 평행한 직선이 만나지 않도록 합니다.

만약 길이가 4인 정사각형 위에 3개의 반직선을 그린다면 다음과 같습니다.

• (3,2) 오른쪽 / (3,3) 왼쪽 / (3,2) 위쪽

따라서 중첩 점의 개수는 2개입니다.

 

플레이어가 주어진 모든 반직선을 그린 뒤 생기는 중첩 점의 개수를 구해보자.

---

FOCUS ON

• 해당 칸에 가로선이 몇개 지나가는지, 세로선이 몇 개 지나가는지 저장해 줍니다.
• (y, x) 칸에 가로선 2개, 세로선 1개가 지나간다면 교차점은 2*1인 2개입니다.
• 마지막 22번 FAIL이 뜬다면, long형을 고려해야 합니다.

 

전체 코드 + 주석

import java.io.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		int n = Integer.parseInt(s[0]); //정사각형 길이
		int m = Integer.parseInt(s[1]); //반직선 개수
		
		long[][][] square = new long[n][n][2]; // n*n 정사각형 0: 가로선, 1: 세로선
		for(int i=0;i<m;i++){  //정사각형에 있는 선 그리기
			s = br.readLine().split(" ");
			
			int y=Integer.parseInt(s[0])-1; //square는 (0,0)부터 시작되기 때문에 y, x좌표에서 1 빼줘야 함.
			int x=Integer.parseInt(s[1])-1;
			
			square = drawLine(y,x,s[2],n,square); // (y,x)에서 시작해 방향이 s[2]인 반직선을 그리는 함수.
		}
		
		long answer=0; //교차점 총 개수
		for(int i=0;i<n;i++){ // square칸을 모두 돌면서
			for(int j=0;j<n;j++){
				answer+=square[j][i][0]*square[j][i][1]; //(j,i)칸에서 가로선, 세로선이 몇 번 만나는지 세기.
			}
		}
		System.out.println(answer);
		
	}
	// (y,x)에서 시작해서 dir방향으로 반직선을 위치에 가로선, 세로선을 추가해줍니다.
	static long[][][] drawLine(int y, int x, String dir, int n, long[][][] square){
		
		int[] dx={1,-1,0,0}; // 우, 좌
		int[] dy={0,0,1,-1}; // 상, 하
 		
		int d=-1;//방향
		if(dir.equals("U")) d=3;
		else if(dir.equals("D")) d=2;
		else if(dir.equals("L")) d=1;
		else d=0;
		
		while(x>=0 && x<n && y>=0 && y<n){//정사각형 범위 안에 있을 때까지 라인 그리기
			
			if(d==0 || d==1){//반직선 방향이 왼쪽 or 오른쪽이면
				square[y][x][0]+=1;//(y,x)칸에 가로선 추가
				
			}else{ //반직선 방향이 위, 아래 일 경우
				square[y][x][1]+=1; //세로선 추가
			}
			x+=dx[d];//다음 위치로 이동
			y+=dy[d];
		}
		
		return square;
	}
}