아이템 줍기
단순한 BFS문제라고 생각했으나 아니었음 ㅋ
우선 문제를 해결하기 위해 나는
그래프를 컴퓨터가 알아볼 수 있는 형식으로 그려야한다고 생각했다.
import java.util.*;
class Solution {
static int[][] board;
static int[] dx = {1, -1, 0, 0}; // 상하좌우
static int[] dy = {0, 0, 1, -1}; // 상하좌우
static boolean[][] visited;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
// board 크기는 101x101로 충분히 크게 설정
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0];
int y1 = rec[1];
int x2 = rec[2];
int y2 = rec[3];
//x축 채우기
//위의 방법을 사용하면 말 그대로 사각형의 안쪽만 비어있게 된다.
//둘이 겹쳐지게 된다면 이 방법은 사용할 수 없음
//1로채우기
// for(int x = x1; x<=x2; x++){
// for(int y =y1; y<y2; y++){
// board[x][y] =1;
// }
// }
// //0으로 테두리만 남기기
// for(int x = x1+1; x<x2; x++){
// for(int y =y1+1; y<y2-1; y++){
// board[x][y] =0;
// }
//테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
for(int i=0; i<13; i++){
for(int k=0; k<13; k++){
System.out.print(board[i][k]+ " ");
}
System.out.println();
}
return 0;
}
}
첫 시도
처음에는 범위내에 있는 모든 값을 1로 채우고 안에 있는 것을 0으로 바꿔주는 방식으로 선택했다.
박스가 하나인 경우는 내가 원하는대로 잘 나오는 것을 확인할 수 있었다
하지만 여러개일땐 달랐다 엉어엉엉엉
두 번째 시도 테두리만 그려보기
import java.util.*;
class Solution {
static int[][] board;
static int[] dx = {1, -1, 0, 0}; // 상하좌우
static int[] dy = {0, 0, 1, -1}; // 상하좌우
static boolean[][] visited;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
// board 크기는 101x101로 충분히 크게 설정
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0];
int y1 = rec[1];
int x2 = rec[2];
int y2 = rec[3];
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
for(int i=0; i<13; i++){
for(int k=0; k<13; k++){
System.out.print(board[i][k]+ " ");
}
System.out.println();
}
return 0;
}
}
이제 테두리가 겹치는부분을 0으로 메꿔야한다...
위 방식들의 문제점
사실 위 방식들이 모두 추구하는 것은 똑같다.
내가 원하는 도표로 그리는 것
하지만 한 가지 문제점이 있는데
이렇게 표현할 수 없는 경우이다.
좀 더 자세하게 표현하자면
내가 원하는 그래프 모양으로 만드려면 어떻게 해야할까?
저런식으로 표현되면 우리가 원하는 답을 잘 얻을 수 없다. 그럼 어떻게 표현해야 할까?
왼쪽은 원래 원하는 경로이고 오른쪽은 아니다!!!
해결안1. 그래프를 키워보기
왼쪽의 그래프를 2배로 변경하면 오른쪽처럼 된다.
그러면 ㄷ자 커브도 처리할 수 있게 된다!
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0]*2;
int y1 = rec[1]*2;
int x2 = rec[2]*2;
int y2 = rec[3]*2;
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1 + 1; j < y2; j++) {
board[i][j] = 0; // 내부 비우기
}
}테두리를 만드는 로직이다.
내부를 위처럼 비우면 아래와 같은 현상이 발생한다. 우리는 테두리를 제외하고 전부다 뺄 예정이니까
// board 크기는 101x101로 충분히 크게 설정
board = new int[55][55];
visited = new boolean[55][55];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0]*2;
int y1 = rec[1]*2;
int x2 = rec[2]*2;
int y2 = rec[3]*2;
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
// 내부 채우기 방지: 경계 내부의 좌표를 0으로 유지
for (int[] rec : rectangle) {
int x1 = rec[0] * 2;
int y1 = rec[1] * 2;
int x2 = rec[2] * 2;
int y2 = rec[3] * 2;
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1 + 1; j < y2; j++) {
board[i][j] = 0; // 내부 비우기
}
}
}이렇게 표시하는게 끝나고 내부를 비워주면 된다.
왜 for을 저렇게 도는지는!...
우선 기본적인 사이즈가 있었다고 치자 우리는 그 사이즈에서 2배 증가시킨 값을 기준으로 그래프를 그린다.
그러니까 원래 좌표값 +1의 크기가 내부사이즈가 되는 것이다. 그림을 보면 이해가 훨씬 편하다!
그림으로 그려서 규칙을 찾을 수 있었다
그래프 테두리 탐색하기
테두리는 시작접에서 bfs를 돌아주면 되는데 이때 테두리인 부분(1로 설정된 부분)만 돌면서 item의 위치에 도달하면 답을 리턴하면된다. 이건 하도 많이 풀어봤으니 패스
private static int bfs(int startX, int startY, int itemX, int itemY){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{startX, startY,0});
visited[startX][startY] =true;
while(!queue.isEmpty()){
int[] cur =queue.poll();
int x = cur[0];
int y = cur[1];
int dist = cur[2];
for(int dir =0; dir<4; dir++){
int nx = x + dx[dir];
int ny = y +dy[dir];
if(nx<0 || ny <0 || nx>=101|| ny>=101)continue;
if(itemX==x && y ==itemY){
return (dist+1)/2;
}
if(board[nx][ny] ==1 && !visited[nx][ny]){
visited[nx][ny] =true;
queue.add(new int[]{nx,ny,dist+1});
}
}
}
return -1;
}
참고로 전해지는 인자는 모두 *2 가 된 상태에서 보내야한다.!!
최종 코드
import java.util.*;
class Solution {
static int[][] board;
static int[] dx = {1, -1, 0, 0}; // 상하좌우
static int[] dy = {0, 0, 1, -1}; // 상하좌우
static boolean[][] visited;
private static int bfs(int startX, int startY, int itemX, int itemY){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{startX, startY,0});
visited[startX][startY] =true;
while(!queue.isEmpty()){
int[] cur =queue.poll();
int x = cur[0];
int y = cur[1];
int dist = cur[2];
for(int dir =0; dir<4; dir++){
int nx = x + dx[dir];
int ny = y +dy[dir];
if(nx<0 || ny <0 || nx>=101|| ny>=101)continue;
if(itemX==x && y ==itemY){
return (dist+1)/2;
}
if(board[nx][ny] ==1 && !visited[nx][ny]){
visited[nx][ny] =true;
queue.add(new int[]{nx,ny,dist+1});
}
}
}
return -1;
}
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
// board 크기는 101x101로 충분히 크게 설정
board = new int[101][101];
visited = new boolean[101][101];
// 2배 확대하여 좌표를 더 정확하게 관리
for (int[] rec : rectangle) {
int x1 = rec[0]*2;
int y1 = rec[1]*2;
int x2 = rec[2]*2;
int y2 = rec[3]*2;
//x축 채우기
// //테두리만 입력하는 방법
//x기준 먼저 채우기
for(int x = x1; x<=x2; x++){
board[x][y1] = 1;
board[x][y2]=1;
}
//y기준 테두리 표시하기
for (int y = y1; y <= y2; y++) {
board[x1][y] = 1; // 좌측 경계
board[x2][y] = 1; // 우측 경계
}
}
// 내부 채우기 방지: 경계 내부의 좌표를 0으로 유지
for (int[] rec : rectangle) {
int x1 = rec[0] * 2;
int y1 = rec[1] * 2;
int x2 = rec[2] * 2;
int y2 = rec[3] * 2;
for (int i = x1 + 1; i < x2; i++) {
for (int j = y1 + 1; j < y2; j++) {
board[i][j] = 0; // 내부 비우기
}
}
}
// BFS를 통해 최단 거리 계산
return bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
}
}
REVIEW
아이디어를 생각해내는게 조금 어려웠던 문제 살짝 예전에 백준에서 풀었던 벌집같은 문제랑 비슷하다는 생각이 들었다
열심히 연습해서 꼭 풀수 있도록 노력하자...
Yellta가 BE개발해요! 왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜왜 가 제일 중요하죠