아이템 줍기 프로그래머스(lv3)(bfs)

import java.util.LinkedList;
import java.util.Queue;

class Solution {
	public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
		int answer = 0;
		//최단거리니 bfs
		//겹치는 부분이 선따라 움직이지않고 건너뛸 수 있으니 2배늘리고,
		Boolean[][] graph = new Boolean[102][102];

		characterX *=2;
		characterY *=2;
		itemX *=2;
		itemY *=2;

		for(int i = 0 ; i < rectangle.length ; i++) {
			int[] doub = rectangle[i];
            for(int j = 0 ; j < doub.length ; j++){
                doub[j] *=2;
            }
			for(int j = doub[1] ; j<=doub[3] ; j++) {
				for(int k = doub[0] ; k<=doub[2] ;k++) {
					graph[j][k] = (j==doub[1] || j==doub[3] || k==doub[0] || k==doub[2])
							&& graph[j][k] != Boolean.FALSE;
				}
			}
		}
		Queue<Node> que = new LinkedList<>();
		que.add(new Node(characterY , characterX , 0));
		graph[characterY][characterX] = Boolean.FALSE;
		
		int[] divx = {0,0,-1,1};
		int[] divy = {-1,1,0,0};
		
		while(!que.isEmpty()) {
			Node node = que.poll();
			if(node.y == itemY && node.x == itemX) {
				answer = node.count;
				return answer/2;
			}
			
			for(int i = 0 ; i < 4 ; i++) {
				int newy = node.y + divy[i]; 
				int newx = node.x + divx[i];
				if(newy<0 || newx <0 || newy>102 || newx >102) continue;
				if(graph[newy][newx] != Boolean.TRUE) continue;
				que.add(new Node(newy, newx , node.count+1));
				graph[newy][newx] = Boolean.FALSE;
			}
		}
		return answer/2;
	}
}

class Node{
	int y;
	int x;
	int count;
	Node(int y , int x , int count) {
		this.y = y;
		this.x = x;
		this.count = count;
	}
}

 

어려웠던 점

• 테두리를 따라 움직이는데, 입출력 예시 1 처럼 선을 건너뛰고, 공간을 이동하는경우
• 테투리를 따라 움직일 수 있는 배열을 생성하는 것

이 두가지를 떠올리기가 어려운 문제였다.

- 크기를 두배 늘려서 맞닿는 값을 조절했다.

- boolean 이 아닌 Boolean객체를 사용하여

 두가지를 해결했다

 

새로이 안 점

이 문제를 통해 Boolean 객체와 boolean 데이터 타입의 차이를 알았고,

공간을 직접적으로 붙이기보다 간접적으로 이동하지 못하게 하는 꼼수(?) 같은 유연하게 생각하는 방법을 좀 더 고안해

봐야겠다.