참고
문제해설
문제 로직고민
NOTE
이해를 위한 그림
•
BFS를 사용하는데, 외곽선을 어떻게 판단할것인가?
◦
하나의 좌표를 기준으로 했을때 8방향중, 사각형의 영역이 없는 부분이 존재한다면 외곽선이다.
◦
사각형의 공간을 모두 확인한다음, 각 좌표의 8방향중 확인이 되지 않은 공간이 있는지 체크한다.
▪
모든 사각형의 영역을 초기화하는 최악의 경우, 50*50크기로 4번 ⇒ 10000
▪
모든 좌표에서 상하좌우 체크 ⇒ 2500의 모든 좌표에서 *8 ⇒ 20000
◦
최대의 경우에도 사각형의 크기가 작은 문제이므로 충분하다고 판단되어 진행한다.
•
문제를 풀면서 이상하걸 느꼈는데, 2차원 배열은 좌표값으로 위의 평면처럼 나타낼 수 없다.
◦
50 * 50의 크기인 경우 [0][0]은 좌측하단이 아니라, 좌측 상단이 되기 때문
◦
y의 값은 50 - y로 수정한다.
•
위의 공식대로 풀었을때 반례가 생긴다.
◦
이처럼 선의 간격이 1인경우, 그어지지 않은 경로로 이동해버린다.
◦
이후에도 추가적인 고민을 진행했으나, 타임오버로 힌트를 보기로한다.
•
힌트 ⇒ 모든 좌표값을 *2해주면 위의 문제를 해결할 수 있다.
◦
2배로 늘려서 위의 반례를 해결했는데 또 막혔다…
◦
도저히 이유를 몰라서, 반례를 찾는데 배열의 크기가 102여야 한다고한다.
◦
분명 모든 좌표값은 1~50인데 왜 102인지 모르겠지만 통과했다.
◦
추가적으로 찾아보았는데 좌표는 100까지이지만, 움직임을 고려하면 101까지 생갹해야 한다고한다..
작성코드
NOTE
import java.util.*;
class Solution {
boolean[][] map;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
this.map = new boolean[102][102];
boolean[][] visited = new boolean[102][102];
characterX *= 2;
characterY *= 2;
itemX *= 2;
itemY *= 2;
int[][] dir = {{-1,0},{0,1},{1,0},{0,-1}};
// 사각형 영역 체크
for(int[] rect : rectangle){
for(int i = 0; i < 4; i++) rect[i] *= 2;
for(int i = rect[1]; i<= rect[3]; i++){
for(int j = rect[0]; j<= rect[2]; j++){
map[i][j] = true;
}
}
}
Queue<int[]> queue = new LinkedList();
queue.offer(new int[]{characterY, characterX, 0});
visited[characterY][characterX] = true;
int answer = 0;
while(!queue.isEmpty()){
int[] cur = queue.poll();
int move = cur[2];
// System.out.println(cur[0] + " " + cur[1]+ " " + cur[2]);
if(cur[0] == itemY && cur[1] == itemX){
answer = move;
break;
}
for(int i=0; i<dir.length; i++){
int my = cur[0] + dir[i][0];
int mx = cur[1] + dir[i][1];
if(my < 2 || my >= 102 || mx < 2 || mx >= 102) continue;
if(map[my][mx] && !visited[my][mx] && check(my,mx)){
visited[my][mx] = true;
queue.offer(new int[]{my, mx, move+1});
}
}
}
return answer/2;
}
private boolean check(int y, int x){
int[][] dir = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
for(int i=0; i<dir.length; i++){
int my = y + dir[i][0];
int mx = x + dir[i][1];
if(my < 0 || my >= 102 || mx < 0 || mx >= 102) continue;
if(!map[my][mx]) return true;
}
return false;
}
}
Java
복사
다른사람 풀이
NOTE
import java.util.*;
class Solution {
int[][] wh = {{0, 1, 0, -1}, {1, 0, -1, 0}};
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
int answer = 0;
// 모든 값을 두 배로
characterX *= 2;
characterY *= 2;
itemX *= 2;
itemY *= 2;
for(int i = 0; i < rectangle.length; i++) {
var rec = rectangle[i];
rectangle[i] = new int[] { rec[0] * 2, rec[1] * 2, rec[2] * 2, rec[3] * 2};
}
boolean[][] map = new boolean[102][102], vst = new boolean[102][102];
for(int[] rec : rectangle) {
for(int i = rec[0]; i <= rec[2]; i++) {
for(int j = rec[1]; j <= rec[3]; j++) {
map[i][j] = true;
}
}
}
// 테두리만 남겨둔다.
Queue<int[]> q = new LinkedList<>();
for(int i = 1; i <= 100; i++) {
for(int j = 1; j <= 100; j++) {
int inner = 0;
for(int[] rec : rectangle) {
if(rec[0] < i && i < rec[2] && rec[1] < j && j < rec[3]) inner++;
}
if(inner != 0) q.add(new int[] { i, j });
}
}
for(int[] p : q) map[p[0]][p[1]] = false;
// 이후는 일반 bfs
q = new LinkedList<>();
q.add(new int[] { characterX, characterY, 0 });
vst[characterX][characterY] = true;
while(!q.isEmpty()) {
int[] p = q.poll();
if(p[0] == itemX && p[1] == itemY) answer = p[2] / 2;
else {
for(int i = 0; i < 4; i++) {
int x = p[0] + wh[0][i];
int y = p[1] + wh[1][i];
if(0 <= x && 0 <= y && x < 102 && y < 102 && !vst[x][y] && map[x][y]) {
q.add(new int[] {x, y, p[2] + 1});
vst[x][y] = true;
}
}
}
}
return answer;
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•