99클럽 코테 스터디 32일차 TIL / [프로그래머스] 아이템 줍기

오늘의 학습 키워드

---

BFS

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 아이템 줍기
• 난이도: Lv3

풀이

---

import java.util.*;

class Solution {

    static boolean[][] visited = new boolean[101][101];
    static int[][] movable = new int[101][101]; // -1: 이동 불가, 0: 아직 판단 X, 1: 이동 가능
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        characterX *= 2;
        characterY *= 2;
        itemX *= 2;
        itemY *= 2;
        
        for(int i=0; i<rectangle.length; i++) {
            for(int j=0; j<4; j++) {
                rectangle[i][j] *= 2;
            }
            
            for(int x=rectangle[i][0]; x <= rectangle[i][2]; x++) {
                for(int y=rectangle[i][1]; y<=rectangle[i][3]; y++) {
                    movable[y][x] = ((x == rectangle[i][0]) || (x == rectangle[i][2]) || (y == rectangle[i][1] || y == rectangle[i][3])) 
                        && (movable[y][x] == 0 || movable[y][x] == 1) ? 1 : -1;
                }
            }
        }
        
        return bfs(characterX, characterY, itemX, itemY);
    }
    
    public int bfs(int characterX, int characterY, int itemX, int itemY) {
        Queue<Point> queue = new LinkedList<>();
        visited[characterY][characterX] = true;
        queue.offer(new Point(characterX, characterY));
        
        int answer = 0;
        
        while(!queue.isEmpty()) {
            answer++;
            int size = queue.size();
            
            for(int i=0; i<size; i++) {
                Point point = queue.poll();
                
                for(int j=0; j<4; j++) {
                    int nx = point.x + dx[j];
                    int ny = point.y + dy[j];
                    
                    if(nx == itemX && ny == itemY) {
                        return answer / 2;
                    }
                    
                    if(nx >= 2 && ny >= 2 && nx <= 100 && ny <= 100 && movable[ny][nx] == 1 && !visited[ny][nx]) {
                        visited[ny][nx] = true;
                        queue.offer(new Point(nx, ny));
                    }
                }
            }
        }
        
        return -1;
    }
    
    static class Point {
        int x;
        int y;
        
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

접근

• 이 문제에서 BFS로 변을 따라 이동할 때 신경써야 할 포인트 두 가지입니다.
  1. ㄷ자 모양이지만 ㅁ자 모양으로 인식하는 부분
  2. 변이지만 다른 사각형과 겹쳐지는 부분
• 첫 번째 포인트는 BFS를 수행할 때 상하좌우로 이동할 수 있기 때문에 발생하는 문제입니다. 이러한 문제를 해결하기 위해서는 map을 2배로 늘려주는 방법이 있습니다.
  • map을 2배로 늘리게 되면 ㅁ자 모양으로 인식하지 못하게 됩니다. (거리가 2가 되기에 이동할 수 없음)
  • 따라서, 모든 좌표에 대해 2배 곱한 값으로 탐색을 진행하며, 최종적으로 아이템을 찾은 거리를 2로 나누어주면 정답을 도출할 수 있습니다.
• 두 번째 포인트는 사전에 movable 배열을 만들어서 이동 가능한 좌표인지 저장하여 관리합니다.

  for(int i=0; i<rectangle.length; i++) {
      for(int j=0; j<4; j++) {
          rectangle[i][j] *= 2;
      }
      
      for(int x=rectangle[i][0]; x <= rectangle[i][2]; x++) {
          for(int y=rectangle[i][1]; y<=rectangle[i][3]; y++) {
              movable[y][x] = ((x == rectangle[i][0]) || (x == rectangle[i][2]) || (y == rectangle[i][1] || y == rectangle[i][3])) 
                  && (movable[y][x] == 0 || movable[y][x] == 1) ? 1 : -1;
          }
      }
  }

  • movable 배열 값의 의미는 다음과 같습니다.
    • 0: 아직 이동 가능 여부를 판단하지 않은 초기의 상태
    • -1: 이동 불가
    • 1: 이동 가능
  • 이후 movable 값을 초기화 해주는데, 조건문은 다음과 같습니다.
    • (해당 좌표가 변에 위치해 있는가) AND (최초로 접근하는가 OR 이전에 초기화된 값이 이동 가능한가)
      • 이렇게되면 사각형의 변은 1로 채워지고, 내부는 -1로 채워집니다.
      • 초기화된 사각형과 겹치는 사각형이 들어왔을 때, 다른 사각형의 내부(⇒ -1)라면 변이라고 하더라도 이동할 수 없다고 상태를 저장하는 것입니다.
• 위 두 가지 포인트를 사전에 처리해준다면 간단한 BFS로 정답을 도출할 수 있습니다.

  public int bfs(int characterX, int characterY, int itemX, int itemY) {
      Queue<Point> queue = new LinkedList<>();
      visited[characterY][characterX] = true;
      queue.offer(new Point(characterX, characterY));
      
      int answer = 0;
      
      while(!queue.isEmpty()) {
          answer++;
          int size = queue.size();
          
          for(int i=0; i<size; i++) {
              Point point = queue.poll();
              
              for(int j=0; j<4; j++) {
                  int nx = point.x + dx[j];
                  int ny = point.y + dy[j];
                  
                  if(nx == itemX && ny == itemY) {
                      return answer / 2;
                  }
                  
                  if(nx >= 2 && ny >= 2 && nx <= 100 && ny <= 100 && movable[ny][nx] == 1 && !visited[ny][nx]) {
                      visited[ny][nx] = true;
                      queue.offer(new Point(nx, ny));
                  }
              }
          }
      }
      
      return -1;
  }

소요 시간

2시간