공부기록
블록 이동하기 본문
문제
https://programmers.co.kr/learn/courses/30/lessons/60063
코드
import java.util.*;
class Solution {
int mv[][] = {
{-1,0},
{0,1},
{1,0},
{0,-1}
};
int spin[][] = {
{-1,0},
{-1,1},
{0,1},
{1,1},
{1,0},
{1,-1},
{0,-1},
{-1,-1}
};
class Node implements Comparable<Node>{
int row;
int col;
public Node(int row, int col){
this.row = row;
this.col = col;
}
@Override
public int compareTo(Node obj){
if(this.row < obj.row){
return -1;
}else if(this.row > obj.row){
return 1;
}else{
if(this.col < obj.col){
return -1;
}else if(this.col > obj.col){
return 1;
}else{
return 0;
}
}
}
@Override
public String toString(){
return "{ row : " + this.row
+ ", col : " + this.col + "}";
}
public boolean equals(Node obj){
if(this.row == obj.row && this.col == obj.col)
return true;
else
return false;
}
}
class Drone{
int depth;
int dir;
ArrayList<Node> points;
public Drone(int depth, int dir, ArrayList<Node> points){
this.depth = depth;
this.dir = dir;
this.points = points;
}
}
void checkHis(boolean his[][][][], ArrayList<Node> points){
his[points.get(0).row][points.get(0).col][points.get(1).row][points.get(1).col] = true;
}
boolean isAns(Drone drone, Node end){
for(Node point : drone.points)
if(point.row == end.row && point.col == end.col)
return true;
return false;
}
boolean isValid(int board[][], ArrayList<Node> points){
int N = board.length;
for(Node point : points){
if(N <= point.row || point.row < 0 || N <= point.col || point.col < 0)
return false;
if(board[point.row][point.col] == 1)
return false;
}
return true;
}
boolean isVisit(boolean his[][][][], ArrayList<Node> list){
if(his[list.get(0).row][list.get(0).col][list.get(1).row][list.get(1).col])
return true;
else
return false;
}
int findDir(ArrayList<Node> list){
int tmp_arr[] = {list.get(1).row - list.get(0).row, list.get(1).col - list.get(0).col};
for(int i=0; i<8; i++)
if(spin[i][0] == tmp_arr[0] && spin[i][1] == tmp_arr[1])
return i;
return -1;
}
public int solution(int[][] board) {
int answer = -1;
Node end = new Node(board.length-1, board.length-1);
Queue<Drone> q = new LinkedList();
boolean his[][][][] = new boolean[board.length][board.length][board.length][board.length];
ArrayList<Node> tmp = new ArrayList<Node>();
tmp.add(new Node(0,1)); tmp.add(new Node(0,0));
Collections.sort(tmp);
checkHis(his, tmp);
Drone sd = new Drone(0, 2, tmp);
q.add(sd);
while(!q.isEmpty()){
Drone cur_drone = q.poll();
if(isAns(cur_drone, end)){
return cur_drone.depth;
}
int c_dir = cur_drone.dir;
ArrayList<Node> c_p = cur_drone.points;
int c_dep = cur_drone.depth;
// System.out.print(c_dep + " : ");
// for(Node p : c_p)
// System.out.print(p + " ");
// System.out.println();
//움직이기
for(int i=0; i<4; i++){
ArrayList<Node> n_l = new ArrayList<>();
for(Node point : c_p){
n_l.add(new Node(point.row+mv[i][0], point.col+mv[i][1]));
}
Collections.sort(n_l);
if(!isValid(board, n_l))
continue;
if(isVisit(his, n_l))
continue;
checkHis(his, n_l);
q.add(new Drone(c_dep+1, c_dir, n_l));
}
int[] offset = {0, 4};
// 90도 회전
for(int i=0; i<2; i++){
Node s_n = c_p.get(i);
int tmp_dir = (c_dir+offset[i])%8;
ArrayList<Node> pred = new ArrayList<>();
for(int j=1; j<=2; j++){
int n_r = s_n.row + spin[(tmp_dir+j)%8][0];
int n_c = s_n.col + spin[(tmp_dir+j)%8][1];
pred.add(new Node(n_r, n_c));
}
if(isValid(board, pred)){
Node n1 = new Node(s_n.row, s_n.col);
Node n2 = new Node(pred.get(1).row, pred.get(1).col);
ArrayList<Node> n_l = new ArrayList<>();
n_l.add(n1); n_l.add(n2);
Collections.sort(n_l);
if(!isVisit(his, n_l)){
checkHis(his, n_l);
// q.add(new Drone(c_dep+1, (tmp_dir+2)%8, n_l));
q.add(new Drone(c_dep+1, findDir(n_l), n_l));
}
}
}
// -90도 회전
for(int i=0; i<2; i++){
Node s_n = c_p.get(i);
int tmp_dir = (c_dir+offset[i])%8;
ArrayList<Node> pred = new ArrayList<>();
for(int j=1; j<=2; j++){
int n_r = s_n.row + spin[(tmp_dir-j+8)%8][0];
int n_c = s_n.col + spin[(tmp_dir-j+8)%8][1];
pred.add(new Node(n_r, n_c));
}
if(isValid(board, pred)){
Node n1 = new Node(s_n.row, s_n.col);
Node n2 = new Node(pred.get(1).row, pred.get(1).col);
ArrayList<Node> n_l = new ArrayList<>();
n_l.add(n1); n_l.add(n2);
Collections.sort(n_l);
if(!isVisit(his, n_l)){
checkHis(his, n_l);
// q.add(new Drone(c_dep+1, (tmp_dir+6)%8, n_l));
q.add(new Drone(c_dep+1, findDir(n_l), n_l));
}
}
}
}
return answer;
}
}피드백
- 한 번 못풀었다가 다시 푼 문제이다.
- 전에 못 푼 이유는 his를 어떻게 제대로 구성하는지 몰라서이다.
- 결국에 첫 번째 점 row, col 과 두 번째 점 row, col 방문 기록인
his[f.row][f.col][s.row][s.col]으로 설계했다.- 첫 번째 좌표와 && 두 번째 좌표 방문 여부를 저장한다.
- 문제는
his[first][second]와his[second][first]가 중복이 된다는 점이다.- 생각을 해보면, 두 점은 순서가 상관없는 집합이다. 즉 조합처럼 임의의 순서를 우리가 그냥 정해서 경우의 수를 구해줄 수가 있다.
- 나는 점 두 개 간 우선순위를 정하여 첫 번째 점, 두 번째 점이 정렬되도록 짯다.
- 그럼 두 개의 경우가 하나의 경우로 통일된다.
- 결국에 첫 번째 점 row, col 과 두 번째 점 row, col 방문 기록인
- his설계를 다하고, 드론을 Queue에 넣어 일반적인 bfs처럼 푼다.
his[f.row][f.col][s.row][s.col]식으로 중복체크를 하면 일반적인 bfs 푸는 것 마냥 풀 수 있다.- 드론은 dir을 넣어서 회전 구현을 좀 더 쉽게 했다.
- 하지만 회전의 경우는 구현이 쉽지는 않았다.
- 두 점을 각각 기준점으로 잡고 90도 회전, -90도 회전하는 경우를 계산하였다.
- 회전이 일어나면서 두 점간이 이루는 방향도 변화가 되지만, 점 간의 우선순위에 의하여 왼쪽에서 오른쪽, 위에서 아래 두 경우의 방향만이 존재한다.
- 이 두 방향만으로 두 점간의 방향이 변하도록 방향 전환을 처리했다.
- 접근하는 아이디어는 단순했으나, 구현 방법과
his[][][][]를 설계하도록 접근하는 것이 어려웠던 문제였다.