풀이 방법
문제를 풀기 위해 테두리를 먼저 구해주었다. 하지만 그냥 테두리를 구하게 되면 ㄷ으로 꺽이는 경로는 컴퓨터 상 경로를 찾기 힘들어서 지형자체를 2배 해서 풀어주었다. 2배 해서 테두리를 구해준 뒤 dfs를 통해 최단 경로를 구해주었다.
아이템 위치를 찾게 되면 아이템은 visited를 다시 false 처리 해줘서 다시 탐색할 수 있도록 하였다.
내 코드
import java.util.*;
class Solution {
static int[][] array;
static int[][] way = {{1,0}, {-1,0}, {0,1}, {0,-1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
static boolean[][] visited;
static int answer = Integer.MAX_VALUE;
public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
array = new int[102][102];
visited = new boolean[102][102];
for(int k = 0; k < rectangle.length; k++){
for(int i = 2 * rectangle[k][0]; i <= 2 * rectangle[k][2]; i++){
for(int j = 2 * rectangle[k][1]; j <= 2 * rectangle[k][3]; j++){
array[i][j] = 1;
}
}
}
for(int k = 0; k < rectangle.length; k++){
for(int i = 2 * rectangle[k][0] + 1; i < 2 * rectangle[k][2]; i++){
for(int j = 2 * rectangle[k][1] + 1; j < 2 * rectangle[k][3]; j++){
array[i][j] = 0;
}
}
}
dfs(characterX * 2, characterY * 2, 0, itemX * 2, itemY * 2);
answer /= 2;
return answer;
}
static void dfs(int x, int y, int len, int itemX, int itemY){
visited[x][y] = true;
if(x == itemX && y == itemY){
answer = Math.min(answer, len);
visited[x][y] = false;
return;
}
for(int i = 0; i < 4; i++){
if(array[x + way[i][0]][y + way[i][1]] == 1 && !visited[x + way[i][0]][y + way[i][1]]){
dfs(x + way[i][0], y + way[i][1], len + 1, itemX, itemY);
}
}
}
}
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
순위 (0) | 2021.10.22 |
---|---|
추석 트래픽 (0) | 2021.10.21 |
교점에 별 만들기 (0) | 2021.10.17 |
뉴스 클러스터링 (0) | 2021.10.08 |
단체 사진 찍기 (0) | 2021.10.08 |