[프로그래머스] 블록 이동하기 / 2020 KAKAO BLIND RECRUITMENT - JAVA

🖇️ 문제 링크

코딩테스트 연습 - 블록 이동하기

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 크기의 지도에서 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다.

https://programmers.co.kr/learn/courses/30/lessons/60063

 

---

📝 문제 분석

평범한 BFS 문제이지만 생각해야 하는 부분이 많았습니다.

방문 체크를 할 때 Set을 통한 Robot(point, point)의 클래스 일치 여부로 판단하였습니다.

가로 → 세로 회전을 할 때 위로 회전을 하려면 위 2칸이 비어있어야 하고, 아래 회전을 하려면 아래 2칸이 비어있어야 합니다. 세로 → 가로 또한 같습니다.

 

 

---

⌨️ 코드

import java.awt.*;
import java.util.*;
import java.util.List;

class Solution {
    int N, ans;
    int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1};
    int[][] map;
    Set<Robot> set = new HashSet<>();

    public int solution(int[][] board) {
        N = board.length;
        map = new int[N + 2][N + 2];
        for(int i = 0; i <= N + 1; i++)
            Arrays.fill(map[i], 1);

        for(int i = 1; i <= N; i++)
            for(int j = 1; j <= N; j++)
                map[i][j] = board[i - 1][j - 1];

        Point E = new Point(N, N);
        Queue<Robot> q = new LinkedList<>();
        Robot S = new Robot(new Point(1, 1) ,new Point(2, 1), 0);
        q.add(S);
        set.add(S);

        while(!q.isEmpty()) {
            Robot cur = q.poll();

            if(cur.p1.equals(E) || cur.p2.equals(E)) {
                ans = cur.d;
                break;
            }

            for(Robot next : getNext(cur)) {
                if(!set.contains(next)) {
                    set.add(next);
                    q.add(next);
                }
            }
        }

        return ans;
    }

    public List<Robot> getNext(Robot cur) {
        Point p1 = cur.p1, p2 = cur.p2;
        List<Robot> next = new ArrayList<>();
        // 4방향
        for(int d = 0; d < 4; d++) {
            Point np1 = new Point(p1.x + dx[d], p1.y + dy[d]);
            Point np2 = new Point(p2.x + dx[d], p2.y + dy[d]);

            if(map[np1.y][np1.x] == 1 || map[np2.y][np2.x] == 1)
                continue;
            next.add(new Robot(np1, np2, cur.d + 1));
        }

        // 가로 -> 세로
        int[] ud = {-1, 1};
        if(p1.y == p2.y) {
            for (int d : ud) {
                if (map[p1.y + d][p1.x] == 0 && map[p2.y + d][p2.x] == 0) {
                    next.add(new Robot(new Point(p1.x, p1.y + d), p1, cur.d + 1));
                    next.add(new Robot(new Point(p2.x, p2.y + d), p2, cur.d + 1));
                }
            }
        } else { // 세로 -> 가로
            for(int d : ud) {
                if(map[p1.y][p1.x + d] == 0 && map[p2.y][p2.x + d] == 0) {
                    next.add(new Robot(new Point(p1.x + d, p1.y), p1, cur.d + 1));
                    next.add(new Robot(new Point(p2.x + d, p2.y), p2, cur.d + 1));
                }
            }
        }

        return next;
    }
}


class Robot {
    Point p1, p2;
    int d;

    Robot(Point p1, Point p2, int d) {
        this.p1 = p1;
        this.p2 = p2;
        this.d = d;
    }

    @Override
    public boolean equals(Object o) {
        Robot robot = (Robot) o;
        return (p1.equals(robot.p1) && p2.equals(robot.p2)) || (p2.equals(robot.p1) && p1.equals(robot.p2));
    }

    @Override
    public int hashCode() {
        return Objects.hash(p1, p2);
    }
}

 

 

 

 

Uploaded by Notion2Tistory v1.1.0