프로그래머스 - 아이템 줍기

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

 

 

 

 

 

문제

출처 : 프로그래머스 아이템 줍기

 

 

• 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현
• 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동한다.
  • 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 된다.
  • 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없다.
  • 지형이 2개 이상으로 분리된 경우도 없다.
  • 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없다.
• rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태로 주어진다.
• 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 주어진다.
• 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리 구하기.

 

제한사항

• 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수
• charcterX, charcterY는 1 이상 50 이하인 자연수
• itemX, itemY는 1 이상 50 이하인 자연수

 

 

 

 

 

풀이

좌표계를 그래프로 표현하고, 바깥쪽 테두리를 구해 그래프 탐색을 이용하여 최단거리를 구하는 문제이다.

 

이 문제의 핵심은 가장 바깥쪽 테두리를 구하는 것이다. 처음 테두리를 구하는 풀이 방법을 떠올리다가 예전에 풀었던 백준 치즈 문제(https://www.acmicpc.net/problem/2636)가 생각이 났다. 치즈 문제에서도 바깥쪽 테두리를 구했어야 했다. 그래서 치즈가 있는 좌표에 대해 4방 탐색을 해서, 빈 공간이 있으면 테두리라고 표시를 했다.

 

 이 문제에도 이 풀이를 적용하려고 했었다. 하지만 변이 직각으로 꺾이는 지점에서의 좌표에 대해서는 4방 탐색을 했을 때, 빈 공간이 아니라 모두 점이다. 치즈 문제에서는 면이라서 가능했지만, 이 문제에서는 점이라서 적용이 어렵다.

 

 그리고 치즈 문제에서는 처음부터 치즈의 그래프가 주어졌다. 하지만 이 문제에서는 직사각형 양 끝점의 좌표 값이 주어지므로 그래프를 그리고, 탐색을 하는 과정은 시간이 오래걸려 비효율적이다.

 

 

• 그래프 표현
  • int 형의 2차원 배열로 각 좌표값을 빈 곳(0), 직사각형 내부(1), 바깥쪽 테두리(2)로 표현현다. 

 

• 가장 바깥쪽 테두리 구하기
  • 입력으로 들어오는 직사각형의 좌표값으로 반복문을 돌린다
    • 좌표가 테두리인 경우 : 빈 곳(0)일 때만 테두리(2)를 그린다. 이미 내부로 칠한 경우(1)라면, 선을 그릴 수가 없기 때문이다.
    • 좌표가 직사각형 내부인 경우 : 직사각형이 겹칠 수 있으므로 테두리(2) 상관없이 모두 내부(1)로 칠한다. 

 

 

이렇게 그래프를 만들고, BFS 탐색을 돌리려고 했다. 하지만 탐색시 걸리는 부분이 있다.

 

1) 바깥쪽 테두리가 ㄷ자로 되어있는 부분

한 점에 대해 4방 탐색을 할 때, 선으로 연결되어 있지 않지만 해당 지점은 테두리이므로 이동이 가능해지게 된다.

 

 

2) 중앙에 빈 공간이 있고, 면적이 1인 경우

한 점에 대해 4방 탐색을 할 때, 안 쪽 테두리로도 이동이 가능해진다. 바깥쪽 테두리만 이동이 가능하므로 안된다.

 

 

 

 

이를 해결할 방법을 계속 생각해보다가 도저히 생각할 수가 없어서 문제 내의 질문하기 게시판에 있는 한 글을 봤다.

(https://school.programmers.co.kr/questions/21253)

 

좌표를 2배로 확장시켜 접근하라는 힌트가 있었다. 좌표를 2배로 확장시키면 위에서 언급했던 문제가 해결된다.

 

 

테두리에 해당이 되어 한칸으로 이동이 가능해졌던 곳이 2배로 늘렸더니 한칸으로 이동이 불가능해지게 된다.

 

 

 

• 좌표계를 2배로 확장하기
  • 그래프 크기를 2배로 만들기 : 제한사항에서 1이상 50이하의 자연수이므로 크기는 50*2+1인 101이 된다.
  • 직사각형의 좌표값을 2배하여 테두리와 내부 채우기
  • 2배된 좌표값으로 그래프 탐색하기

 

 

• BFS 탐색
  • 최소 이동을 구하는 것이므로 너비우선탐색이 적합하다.
  • 큐를 돌릴시 매번 큐의 사이즈만큼 끊어서 탐색한다.
  • 큐에 시작점을 담아 4방으로 탐색하며, 테투리일 시 큐에 담아 계속 탐색한다.
  • 도착했다면 바로 이동 횟수를 return 한다. (최솟값을 구하는 것이므로 더 이상 탐색할 필요가 없다.)

 

 

 

 

 

코드

import java.util.*;

class Solution {
    static int[][] graph; //그래프 : 0, 1(내부), 2(테두리)
    static boolean[][] visited;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    
    static class Point {
        int i, j; //y좌표(행), x좌표(열)
        
        Point(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        graph = new int[50*2+1][50*2+1];
        
        //그래프 영역 채우기
        for(int[] r : rectangle) {
            int x1 = r[0]*2; //좌측 하단 x
            int y1 = r[1]*2; //좌측 하단 y
            int x2 = r[2]*2; //우측 상단 x
            int y2 = r[3]*2; //우측 상단 y
            
            for(int i = y1; i <= y2; i++) {
                for(int j = x1; j <= x2; j++) {
                    if(i == y1 || i == y2 || j == x1 || j == x2) { //좌표가 테두리
                        if(graph[i][j] == 0) { //빈 곳
                            graph[i][j] = 2; //테두리 그리기
                        }
                    } else { //좌표가 내부
                        graph[i][j] = 1; //내부 칠하기        
                    }
                }
            }
        }
        
        //그래프 탐색
        visited = new boolean[50*2+1][50*2+1];
        
        int answer = bfs(characterX * 2, characterY * 2, itemX * 2, itemY * 2) / 2; //2배 늘렸으니 2로 나누기
        return answer;
    }
    
    public int bfs(int characterX, int characterY, int itemX, int itemY) {
        Queue<Point> queue = new LinkedList<>();
        
        queue.add(new Point(characterY, characterX));
        visited[characterY][characterX] = true;
        
        int count = 0; //이동 카운트
        while(!queue.isEmpty()) {
            int size = queue.size(); //너비 탐색을 위한 사이즈
            
            for(int s = 0; s < size; s++) { //사이즈만큼 끊어서 탐색
                Point point = queue.poll();
                
                if(point.i == itemY && point.j == itemX) { //도착
                    return count;
                }
                
                for(int d = 0; d < 4; d++) {
                    int ni = point.i + di[d];
                    int nj = point.j + dj[d];
                    
                    if(1 <= ni && ni <= 100 && 1 <= nj && nj <= 100) {
                        if(!visited[ni][nj] && graph[ni][nj] == 2) {
                            queue.add(new Point(ni, nj));
                            visited[ni][nj] = true;
                        }
                    }
                }
            }
            
            count++;
        } 
        
        return count;
    }
}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 좌표계를 2배로 늘리는 방법도 있음
• x, y와 행, 열 헷갈림 주의하기. 개념이 반대라서 코드 작성시 주의가 필요하다.