[Java] 2021 위클리 챌린지 11주차 - 아이템 줍기

[Java] 2021 위클리 챌린지 11주차 - 아이템 줍기

테두리와 안쪽을 구분해야 한다.

단순하게 좌표의 길이를 2배로 키우면 테두리와 안쪽을 구분하기가 쉬워진다.

1. (짝수, 짝수) 는 점

2. (짝수, 홀수) 와 (홀수, 짝수)는 선분 위

3. (홀수, 홀수)는 내부가 된다.

먼저 모든 사각형을 1로 채워준 다음, 내부를 0으로 채워주면 제일 바깥쪽 테두리만 남게 된다.

이 이후에는 BFS를 통해서 얼마나 걸리는지 확인해주면 된다. 2배로 키워놨기 때문에 정답은 2로 나눈 값이 된다.

class Point{ int x; int y; int depth; public Point(int x, int y, int depth){ this.x = x; this.y = y; this.depth = depth; } } class Solution { public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) { int answer = 0; int n = 105; int m = 105; int[][] board = new int[n][m]; int numR = rectangle.length; //사각형을 1로 채움 for(int i = 0; i < numR; i ++){ int[] r = rectangle[i]; for(int x = r[0] *2; x <= r[2] *2; x ++){ for(int y = r[1] * 2; y <= r[3] * 2; y ++){ board[x][y] = 1; } } } //안쪽을 0으로 채움 for(int i = 0; i < numR; i ++){ int[] r = rectangle[i]; for(int x = r[0] *2 + 1; x <= r[2] *2 - 1; x ++){ for(int y = r[1] * 2 + 1; y <= r[3] * 2 - 1; y ++){ board[x][y] = 0; } } } boolean[][] visited = new boolean[n][m]; int[] dx = {0,0,1,-1}; int[] dy = {1,-1,0,0}; Point start = new Point(characterX * 2, characterY * 2, 0); Queue q = new LinkedList<>(); visited[characterX * 2][ characterY*2] = true; q.add(start); while(!q.isEmpty()){ Point front = q.poll(); if(front.x == itemX * 2 && front.y == itemY *2){ answer = front.depth; break; } for(int k = 0; k < 4; k ++){ int nx = dx[k] + front.x; int ny = dy[k] + front.y; if(!visited[nx][ny] && board[nx][ny] == 1){ q.add(new Point(nx,ny, front.depth + 1)); visited[nx][ny] = true; } } } return answer / 2; } }

반응형

from http://blue-jay.tistory.com/88 by ccl(A) rewrite - 2021-10-23 17:01:10