프로그래머스 87694 아이템 줍기 자바 풀이

난이도 : Lv. 3

풀이일 : 2412183

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

프로그래머스

---

문제

---

풀이 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int answer = 0;
        
        boolean[][] land = new boolean[102][102];
        boolean[][] visited = new boolean[102][102];
        int[] di = {-1, 1, 0, 0, -1, 1, -1, 1};
        int[] dj = {0, 0, -1, 1, -1, -1, 1, 1};
        int i, j, v, ni, nj, ti, tj;
        
        for (int[] info : rectangle) { // 입력 처리
            for (int x = info[1] * 2; x < info[3] * 2 + 1; x++) {
                for (int y = info[0] * 2; y < info[2] * 2 + 1; y++) {
                    land[x][y] = true;
                }
            }
        }
        
        Queue<Integer> queue = new LinkedList<>();
        queue.add(characterY * 2);
        queue.add(characterX * 2);
        queue.add(1);
        visited[characterY * 2][characterX * 2] = true;
        
        while (!queue.isEmpty()) {
            i = queue.poll();
            j = queue.poll();
            v = queue.poll();
            
            for (int k = 0; k < 4; k++) {
                ni = i + di[k];
                nj = j + dj[k];
                if (0 <= ni && ni < 102 && 0 <= nj && nj < 102 && land[ni][nj]) {
                    for (int l = 0; l < 8; l++) { // 외곽선 여부 검사
                        ti = ni + di[l];
                        tj = nj + dj[l];
                        if (0 <= ti && ti < 102 && 0 <= tj && tj < 102 && !land[ti][tj]) {
                            if (!visited[ni][nj]) {
                                queue.add(ni);
                                queue.add(nj);
                                queue.add(v + 1);
                                visited[ni][nj] = true;
                                if (ni == itemY * 2 && nj == itemX * 2) {
                                    return (int) v / 2;
                                }
                            }
                        }
                    }
                }
            }
        }
        return answer;
    }
}

 

---

실행 화면

---

수정 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    class Node {
        int i, j, v;
        
        public Node(int i, int j, int v) {
            this.i = i;
            this.j = j;
            this.v = v;
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        boolean[][] land = new boolean[102][102];
        boolean[][] visited = new boolean[102][102];
        int[] di = {-1, 1, 0, 0, -1, 1, -1, 1};
        int[] dj = {0, 0, -1, 1, -1, -1, 1, 1};
        int ni, nj, ti, tj;
        
        for (int[] info : rectangle) {
            for (int x = info[1] * 2; x < info[3] * 2 + 1; x++) {
                for (int y = info[0] * 2; y < info[2] * 2 + 1; y++) {
                    land[x][y] = true;
                }
            }
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(characterY * 2, characterX * 2, 1));
        visited[characterY * 2][characterX * 2] = true;
        
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            
            for (int k = 0; k < 4; k++) {
                ni = now.i + di[k];
                nj = now.j + dj[k];
                if (0 <= ni && ni < 102 && 0 <= nj && nj < 102 && land[ni][nj]) {
                    for (int l = 0; l < 8; l++) {
                        ti = ni + di[l];
                        tj = nj + dj[l];
                        if (0 <= ti && ti < 102 && 0 <= tj && tj < 102 && !land[ti][tj]) {
                            if (!visited[ni][nj]) {
                                queue.add(new Node(ni, nj, now.v + 1));
                                visited[ni][nj] = true;
                                if (ni == itemY * 2 && nj == itemX * 2) {
                                    return (int) now.v / 2;
                                }
                            }
                        }
                    }
                }
            }
        }
        return 0;
    }
}

수정 내용

• 기존 코드에서 queue에 세 번씩 요소를 넣고 빼던 부분을 Node 클래스를 만들어 수정했다.

---

실행 화면

---

느낀점

• 이제 웃기게 queue에 숫자 두개 세개씩 한 번에 넣고 한 번에 빼고 안하고 좀 그럴듯하게 코드 쓸 수 있다ㅠㅜ
• 아직 다익스트라 문제는 Node로 해결을 못했는데 그거 다시 매달려봐야지.

---

개선 코드

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    class Node { // i, j 좌표, 이동거리 
        int i, j, v;
        
        public Node(int i, int j, int v) {
            this.i = i;
            this.j = j;
            this.v = v;
        }
    }
    
    public int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
        int[][] land = new int[102][102];
        int[] di = {-1, 1, 0, 0};
        int[] dj = {0, 0, -1, 1};
        int ni, nj;
        
        for (int[] r : rectangle) { // 외곽선 정보 저장
            for (int x = r[1] * 2; x < r[3] * 2 + 1; x++) {
                for (int y = r[0] * 2; y < r[2] * 2 + 1; y++) {
                    if (r[1] * 2 < x && x < r[3] * 2 && r[0] * 2 < y && y < r[2] * 2) {
                        land[x][y] = -1;
                    }
                    else if (land[x][y] != -1) {
                        land[x][y] = 1;
                    }
                }
            }
        }
        
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(characterY * 2, characterX * 2, 1));
        land[characterY * 2][characterX * 2] = 0;
        
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            for (int k = 0; k < 4; k++) {
                ni = now.i + di[k];
                nj = now.j + dj[k];
                if (0 <= ni && ni < 102 && 0 <= nj && nj < 102 && land[ni][nj] > 0) {
                    queue.add(new Node(ni, nj, now.v + 1));
                    land[ni][nj] = 0;
                    if (ni == itemY * 2 && nj == itemX * 2) {
                        return (int) now.v / 2;
                    }
                }
            }
        }
        return 0;
    }
}

수정 사항

• 모서리 여부를 반복문으로 확인했었는데, 처음부터 모서리 정보를 저장하고 진행하는 형식으로 수정했다.

---

실행 화면

• 파이썬은 이 방식으로 수정하니까 더 빨라졌는데 자바는 오히려 더 느려졌다.