https://programmers.co.kr/learn/courses/30/lessons/87694
코딩테스트 연습 - 아이템 줍기
[[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10
programmers.co.kr
처음에 어떻게 풀어야 할지 감이 안 와서 고민해보다가 다른 분들의 힌트를 봤다. 생활 패턴 고친다고 밤을 새워서 그런지(핑계 맞음ㅎㅎ) 봐도 무슨 말인지 모르겠더라. 짐 싸서 집 가는 길에 백준에서 비슷한 문제를 풀었던 기억이 갑자기 떠올랐다ㅋㅋ. 신기하게도 샤워하거나 산책하면 아이디어가 잘 떠오르는데, 이유는 뭘까?
아무튼 DFS나 BFS로 풀 수 있다는 것까진 알았는데, 이번엔 어떻게 테두리만 표시할지 떠오르지 않았다. 결국 다른 분의 풀이를 봤는데, 대단한 사고력이 필요하진 않았고 오히려 방법이 단순했다. 최근에 코테 실력이 많이 는 것 같아서 "나 이제 코테 좀 치나?ㅋㅋ" 싶었는데, 반성했다.
결론적으론 나에게 어려운 문제였다.
요약
- 좌표 및 사각형 영역을 2배로 늘린다
- 그래프에 모든 사각형의 테두리를 표시한다. (1 vs 0 or true vs false)
- 사각형의 테두리를 제외한 안쪽 영역(너비)을 빈공간으로 표시한다.
- 테두리 전체 길이(S)와 시작점에서 도착점(src- dst)까지의 길이를 각각 구한다.
- 정답: min(S - (src - dst), src - dst)
풀이
1. DFS/BFS로 해결할 수 있다
그래프를 점과 빈공간으로 표시할 때, 테두리만을 나타낼 수 있으면 시작점에서 도착점까지 얼마나 이동했는지를 DFS/BFS로 알 수 있다.
2. 좌표를 늘린다!
테두리를 따라가려면 인접한 1을 탐색하면 된다. 하지만 테두리간 거리가 1이면 위와 같은 상황에서 테두리를 잘못 따라갈 수 있다. 따라서, 좌표를 모두 2배로 늘려서 위와 같은 문제를 예방한다.
3. 어떻게 바깥의 테두리만 표시할 수 있을까?
1. 우선 모든 사각형의 테두리를 표시한다.
2. 테두리 안쪽 영역을 빈공간으로 표시한다. 그럼 사각형에 포함되어 있던 테두리가 제거된다.
코드
class Solution {
static final int SIZE = 101;
static boolean[][] board = new boolean[SIZE][SIZE]; // true: 점
int[] dR = new int[]{-1, 1, 0, 0};
int[] dC = new int[]{0, 0, -1, 1};
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
// 좌표 2배로 늘리기
int srcRow = characterY * 2;
int srcCol = characterX * 2;
int dstRow = itemY * 2;
int dstCol = itemX * 2;
markRect(rectangle); // 그래프에 사각형 테두리만 표시
// + 1: 마지막 위치에서 시작점으로 돌아온 거리
int totalDistance = findDistance(srcRow, srcCol, srcRow, srcCol, new boolean[SIZE][SIZE], 0) + 1;
int distance = findDistance(srcRow, srcCol, dstRow, dstCol, new boolean[SIZE][SIZE], 0);
return Math.min(distance, totalDistance - distance) / 2;
}
private void markRect(int[][] rectangles) {
for (int[] rect: rectangles) {
int firstRow = 2* rect[1];
int firstCol = 2* rect[0];
int secondRow = 2* rect[3];
int secondCol = 2* rect[2];
markEdge(firstRow, firstCol, secondRow, secondCol);
}
for (int[] rect: rectangles) {
int firstRow = 2* rect[1];
int firstCol = 2* rect[0];
int secondRow = 2* rect[3];
int secondCol = 2* rect[2];
markSpace(firstRow, firstCol, secondRow, secondCol);
}
}
// 그래프에 테두리 모두 표시
private void markEdge(int firstRow, int firstCol, int secondRow, int secondCol) {
for(int row = firstRow; row <= secondRow; row++) {
board[row][firstCol] = true;
}
for(int col = firstCol + 1; col <= secondCol; col++) {
board[secondRow][col] = true;
}
for(int row = secondRow - 1; row >= firstRow; row--) {
board[row][secondCol] = true;
}
for (int col = secondCol - 1; col > firstCol; col--) {
board[firstRow][col] = true;
}
}
// 테두리를 제외한 사각형 너비 영역을 모두 빈공간으로 표시한다
private void markSpace(int firstRow, int firstCol, int secondRow, int secondCol) {
for (int row = firstRow + 1; row < secondRow; row++) {
for (int col = firstCol + 1; col < secondCol; col++) {
board[row][col] = false;
}
}
}
// DFS
private int findDistance(int row, int col, final int dstRow, final int dstCol, final boolean[][] visited, int count) {
if (count > 0 && row == dstRow && col == dstCol) {
return count;
}
visited[row][col] = true;
for (int i = 0; i < 4; i++) {
int newRow = row + dR[i];
int newCol = col + dC[i];
if (newRow >= 0 && newRow < SIZE && newCol >= 0 && newCol < SIZE && board[newRow][newCol] && !visited[newRow][newCol]) {
return findDistance(newRow, newCol, dstRow, dstCol, visited, count+1);
}
}
return count;
}
}'Problem Solving > 프로그래머스' 카테고리의 다른 글
| 프로그래머스: 입국 심사 (Kotlin) (0) | 2022.04.04 |
|---|---|
| 프로그래머스: 프린터 (Kotlin) (0) | 2022.03.31 |
| [프로그래머스] 순위 (Kotlin) - 플로이드 와샬 사용하지 않고 풀기 (0) | 2022.02.14 |
| (Kotlin) 프로그래머스 - 표 편집 [2021 카카오 채용연계형 인턴십] (0) | 2022.01.07 |
| (Kotlin) 프로그래머스 - 오픈채팅방 [2019 KAKAO BLIND RECRUITMENT] (0) | 2021.08.23 |
