🧶 설명
레벨: 3
언어: 자바(Java)
👜 느낀점
이문제는 너비우선탐색 문제인데,
사각형들의 모음으로 외변을 따라서 길을 이용해야되는데
풀어보니 주의할점이 2가지 있더라(아래 사진을 준비했다)
주의할점
- (보라색 표시) 직사각형이 겹치면 해당경로들이 안쪽으로 들어가는데 이경우 제외 필요
- (하늘색 표시) 좌표로 표시하면 (3,5) 와 (3,6)이 방문가능한 경로인데 단순하게 가능한 경우로 했을시 하늘색으로 표시해둔 경로로 이동되는 경우가 있다 이를 어떻게 해야될지??
풀이방법에서 주의할점을 같이 말씀드려보겠습니다.
1. Boolean 배열은 준비한다(상태가 null, true, false 3개 필요)
2. 하늘색 표시한것처럼 단순히 지금숫자대로 이용하면 예외케이스가 발생하는 경우가 있어서 전체적인 숫자를 2배로 불린다.(하늘색 표시일경우 바로 맞다지가 않게됨)
3. 직사각형 루프를 돌리고 Boolean 배열 기본값이 null인데, 직사각형 내부에 있는 좌표들은 다 false처리를 하고 빗변은 true로 하는데, 다른 직사각형을 다시 확인시 안되는 경로들은 true 변경하지 못하게 하고, 확인안한 null일 경우만 true 변경이 가능하게 하기위함입니다
4. 첫번째 위치와 이동에 따른 흔적을 담을 queue 선언
5. 도착위치가 같고 카운팅숫자가 루프돌리면서 얻은 최소치보다 아래면 값 변경
6. 좌표외 위치일시 길이 아닌곳인 경우는 제외
7. 최종적으로 2배 불린걸 나누기 2로해서 반환
이런 방식으로 풀었습니다
⛑ 내가 작성한 코드
import java.util.*;
class Solution {
static final int[] moveX = new int[]{1, -1, 0, 0},
moveY = new int[]{0, 0, 1, -1};
static class Node {
int x;
int y;
int count;
public Node(int x, int y, int count) {
this.x = x;
this.y = y;
this.count = count;
}
}
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
Boolean[][] roadway = new Boolean[102][102];
characterX *= 2;
characterY *= 2;
itemX *= 2;
itemY *= 2;
for(int i = 0; i < rectangle.length; i++) {
int[] nowRec = rectangle[i];
for(int j = 0; j < 4; j++) nowRec[j] *= 2;
for(int x = nowRec[0]; x <= nowRec[2]; x++) {
for(int y = nowRec[1]; y <= nowRec[3]; y++) {
roadway[x][y] = (x == nowRec[0] || x == nowRec[2] ||
y == nowRec[1] || y == nowRec[3]) && roadway[x][y] != Boolean.FALSE;
}
}
}
Queue<Node> queue = new LinkedList<>();
roadway[characterX][characterY] = false;
queue.offer(new Node(characterX, characterY, 0));
int min = Integer.MAX_VALUE;
while(!queue.isEmpty()) {
Node node = queue.poll();
if(node.x == itemX && node.y == itemY && min > node.count) {
min = node.count;
continue;
}
for(int i = 0; i < 4; i++) {
int x = node.x + moveX[i], y = node.y + moveY[i];
if(x < 2 || y < 2 || x > 100 || y > 100) continue;
if(roadway[x][y] != Boolean.TRUE) continue;
roadway[x][y] = false;
queue.offer(new Node(x, y, node.count + 1));
}
}
return min / 2;
}
}🏅 가장 좋아요 많이 받은 코드
import java.util.*;
class Solution {
static String[][] shape;
static int startX, startY, targetX, targetY, answer, total;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
shape = new String[52][52];
startX = characterX; startY = characterY; targetX = itemX; targetY = itemY;
answer = total = 0;
for(int i=0; i<52; i++) Arrays.fill(shape[i],""); // ""로 초기화
for(int[] xy : rectangle){
int leftX = xy[0], rightX = xy[2], leftY = xy[1], rightY = xy[3];
// 꼭지점 (왼쪽아래(LDX), 오른쪽아래(RDX), 왼쪽위(LUX), 오른쪽위(RUX))
shape[leftX][leftY] = "LDX"; shape[rightX][leftY] = "RDX"; shape[leftX][rightY] = "LUX"; shape[rightX][rightY] = "RUX";
for(int x=leftX+1; x<rightX; x++){// 상(U), 하(D)
shape[x][rightY] += "U"; shape[x][leftY] += "D";
}
for(int y=leftY+1; y<rightY; y++){// 좌(L), 우(R)
shape[leftX][y] += "L"; shape[rightX][y] += "R";
}
}
followLine(characterX, characterY);
return Math.min(answer, total-answer);
}
public void followLine(int x, int y){
String location = shape[x][y];
if(location.equals("RU") || location.equals("UR") || location.equals("LUX") || location.equals("U")) x++;
if(location.equals("LD") || location.equals("DL") || location.equals("RDX") || location.equals("D")) x--;
if(location.equals("LU") || location.equals("UL") || location.equals("LDX") || location.equals("L")) y++;
if(location.equals("RD") || location.equals("DR") || location.equals("RUX") || location.equals("R")) y--;
total++;
if(x == targetX && y == targetY) answer = total;
if(x == startX && y == startY) return;
followLine(x, y);
}
}