[코딩테스트] Java 아이템 줍기

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

해당 문제는 검은색 선을 따라서만 이동할 수 있다는 것이 포인트였습니다.
예를 들어, 도형의 변이 다음과 같을 때 BFS/DFS를 할 때에 문제가 발생할 수 있습니다.
(4,3) -> (4,4) -> (5,3) -> ...
왜냐하면 저희가 현재까지 사용했던 dx/dy 테크닉을 사용하게 되면 (4,3)에서 (5,3)으로 바로 이동할 수 있기 때문입니다.

 

따라서 저는 Scale(2)을 두어 더 정교하게 이동할 수 있도록 하였습니다.
나중에 답을 구할 때에도 Scale의 값만큼 나누어줘야하는 주의사항이 있습니다.

 

소스코드

import java.util.*;

class Solution {
    
    int answer = 0;
    final int SIZE = 101;
    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int[][] map = new int[SIZE][SIZE];
    boolean[][] visited = new boolean[SIZE][SIZE];
    Queue<Pair> q = new LinkedList<>();
    
    class Pair {
        int x, y, cnt;
        
        public Pair(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
    
    public boolean inRange(int x, int y) {
        return 0 <= x && x < SIZE && 0 <= y && y < SIZE;
    }
    
    public boolean canGo(int x, int y) {
        if(!inRange(x, y)) return false;
        if(map[x][y] != 1 || visited[x][y]) return false;
        return true;
    }
    
    public void bfs(int startX, int startY, int itemX, int itemY) {
        visited[startX][startY] = true;
        q.add(new Pair(startX, startY, 0));
        
        while(!q.isEmpty()) {
            Pair cur = q.poll();
            
            if(cur.x == itemX && cur.y == itemY) {
                answer = cur.cnt/2;
                return;
            }
            
            for(int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                if(canGo(nx, ny)) {
                    q.add(new Pair(nx, ny, cur.cnt + 1));
                    visited[nx][ny] = true;
                }
            }
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        
        int n = rectangle.length;
        // 도형 바깥쪽은 1, 안쪽은 2
        // map이 2이면 도달 불가능
        // map부분이 이상함. 다시 생각하기. 그림 그려야 할 듯?
        for(int i = 0; i < n; i++) {
            int x1 = rectangle[i][0] * 2;
            int y1 = rectangle[i][1] * 2;
            int x2 = rectangle[i][2] * 2;
            int y2 = rectangle[i][3] * 2;
            for(int p = x1; p <= x2; p++) {
                for(int q = y1; q <= y2; q++) {
                    if(p == x1 || p == x2 || q == y1 || q == y2) {
                        if(map[p][q] == 0) {
                            map[p][q] = 1;    
                        }
                    } else {
                        map[p][q] = 2;
                    }
                }
            }
        }
        
        bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);
        
        return answer;
    }
}

코드 설명

• Pair 클래스
  • 좌표를 나타내는 x와 y를 저장하는 좌표와 현재 step의 값을 저장하는 클래스입니다.
  • BFS 탐색 시 현재 위치를 나타내기 위해 사용됩니다.

public boolean inRange(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

public boolean canGo(int x, int y) {
    if(!inRange(x, y)) return false;
    if(visited[x][y] || globalMaps[x][y] == 0) return false;
    return true;
}

• inRange 메소드
  다음 탐색해야하는 좌표가 배열 내부인지 확인하기 위한 메소드
• canGo 메소드
  다음 탐색해야하는 좌표로 이동이 가능한지 확인하기 위한 메소드(배열 내인지, 방문한 좌표인지, 다음 좌표가 벽인지)

public void bfs(int startX, int startY, int itemX, int itemY) {
    visited[startX][startY] = true;
    q.add(new Pair(startX, startY, 0));

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

        if(cur.x == itemX && cur.y == itemY) {
            answer = cur.cnt/2;
            return;
        }

        for(int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if(canGo(nx, ny)) {
                q.add(new Pair(nx, ny, cur.cnt + 1));
                visited[nx][ny] = true;
            }
        }
    }
}

• bfs 메소드
  • 큐에 현재 위치와 이동 횟수를 저장합니다.
  • 상하좌우 네 방향을 탐색하며 이동 가능(canGo)한 경우 큐에 추가합니다.
  • 목표 위치(itemX, itemY)에 도달하면 이동 횟수 / 2한 값을 저장합니다.

public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
    int n = rectangle.length;
    // 도형 바깥쪽은 1, 안쪽은 2
    // map이 2이면 도달 불가능
    // map부분이 이상함. 다시 생각하기. 그림 그려야 할 듯?
    for(int i = 0; i < n; i++) {
        int x1 = rectangle[i][0] * 2;
        int y1 = rectangle[i][1] * 2;
        int x2 = rectangle[i][2] * 2;
        int y2 = rectangle[i][3] * 2;
        for(int p = x1; p <= x2; p++) {
            for(int q = y1; q <= y2; q++) {
                if(p == x1 || p == x2 || q == y1 || q == y2) {
                    if(map[p][q] == 0) {
                        map[p][q] = 1;    
                    }
                } else {
                    map[p][q] = 2;
                }
            }
        }
    }

    bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2);

    return answer;
}

• solution 메소드
  • 모든 사각형(rectangle)을 테두리(1)와 내부(2)로 분류하여 map에 저장합니다.
  • 좌표 확장
    • 좌표를 *2하여 지도 상에서 모든 이동을 정수 단위로 표현합니다.
  • BFS를 이용해 시작 위치에서 목표 위치까지 탐색합니다.
•