99클럽 코테 스터디 12일자 TIL + 게임 맵 최단거리

문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/1844 (프로그래머스)

학습 키워드

DFS/BFS

시도 방법

(1) 큐를 활용한 BFS 방식으로 문제 풀이

내가 작성한 코드

첫번째 시도 (실패)

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

class Solution {
    public int solution(int[][] maps) {    
    
        //이동좌표
        int x[] = new int[]{0 , 1 , 0 , -1}; // 순서대로 위,오른쪽,아래,왼쪽 x좌표 이동
        int y[] = new int[]{-1 , 0 , 1 , 0}; // 순서대로 위,오른쪽,아래,왼쪽 y좌표 이동
    
        //방문할 곳을 저장할 큐 공간
        Queue<Position> queue = new LinkedList<>(); 
        int n = maps.length; 
        int m = maps[0].length; 
        
        //경로를 업데이트할 map 정보를 클론
        int[][] updatedMap = new int[n][m]; 
        for(int i = 0 ; i < maps.length; i++) {
            updatedMap[i] = maps[i].clone();           
        }
        
        boolean visited[][] = new boolean[n][m]; 
        
        //현재 위치 방문 처리
        visited[0][0] = true; 
        queue.offer(new Position(0,0)); 
        
        while(!queue.isEmpty()) { 
        
            
            Position now = queue.poll(); 
            
            int nowX = now.getX(); 
            int nowY = now.getY(); 
            visited[nowX][nowY] = true; 

            //사방 체크 
            for(int i = 0 ; i<4; i++) {
                
                int nextX = nowX + x[i];
                int nextY = nowY + y[i];
                //벽이거나 범위를 넘어서면 continue 처리
                if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= m || 
                   maps[nextX][nextY] == 0 || visited[nextX][nextY]) {
                    continue; 
                } else { 
                    
                    queue.offer(new Position(nextX , nextY)); 
                    updatedMap[nextX][nextY] = updatedMap[nowX][nowY] + 1 ; 
                    //그렇지 않으면 queue에 추가하고 
                    //동시에 다음값 = 다음값 + 현재값으로 업데이트 (사실상 1)
                }
            }
        }

        /* 
        //값 체크 용
        for(int i = 0 ; i<n; i++) {
            System.out.println(""); 
            for(int j = 0 ; j<m; j++) {
               System.out.print(maps[i][j] + " ");  
            }
        }
        System.out.println(" ") ; 

        for(int i = 0 ; i<n; i++) {
            System.out.println(""); 
            for(int j = 0 ; j<m; j++) {
               System.out.print(updatedMap[i][j] + " ");  
            }
        }
        */
        return updatedMap[n-1][m-1] == 1 ? -1 : updatedMap[n-1][m-1];
    }
}

class Position {
    private int x ; 
    private int y ; 
    
    public Position(int x , int y) {
        this.x = x; 
        this.y = y; 
    }
    
    public int getX() {
        return this.x; 
    }
    public int getY() {
        return this.y ; 
    }
}

코드설명

먼저 미로의 이동을 표현하기 위해 int x[] , int y[] 배열을 활용하여 방향을 구현했다.
예를 들어 x[0] 과 y[0] 은 각각 0 , -1 을 의미하는데 현재 위치가 (1,1) 이고 이 값을 각각 더하면 (1 , 0 ) 이 되어 "위"를 의미하게 된다.

BFS 기법을 사용할 거라서 큐를 이용했고 큐에 저장할 값은 Position이라는 클래스를 만들어 x,y 좌표가 저장되도록 설계했다.

현재 위치를 기준으로 인접한 데이터 중 이미 방문을 했거나 (visited가 true) 벽(1) 이거나 범위를 넘어서버리면 큐에 넣지 않고, 그 외에는 큐에 추가하여 다음 while문에 출력되도록 했다.

출력결과

효율성에서 실패를 했다.

두번째 시도 (성공)

방문처리 코드만 변경했는데 효율성이 통과되었다.
어떤 원리인지는 아래 "새롭게 알게된 점" 에서 설명한다.

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

class Solution {
    public int solution(int[][] maps) {    
    
        //이동좌표
        int x[] = new int[]{0 , 1 , 0 , -1}; // 순서대로 위,오른쪽,아래,왼쪽 x좌표 이동
        int y[] = new int[]{-1 , 0 , 1 , 0}; // 순서대로 위,오른쪽,아래,왼쪽 y좌표 이동
    
        int n = maps.length; 
        int m = maps[0].length; 
        boolean visited[][] = new boolean[n][m]; 
        
        //방문할 곳을 저장할 큐 공간
        Queue<Position> queue = new LinkedList<>(); 
        
        //현재 위치를 큐에 추가
        queue.offer(new Position(0,0)); 
        
        while(!queue.isEmpty()) { 
        
            Position now = queue.poll();             
            int nowX = now.getX(); 
            int nowY = now.getY(); 
//            visited[nowX][nowY] = true; 방문처리를 여기서 하지 말라고? 

            //사방 체크 
            for(int i = 0 ; i<4; i++) {
                
                int nextX = nowX + x[i];
                int nextY = nowY + y[i];
                //벽이거나 범위를 넘어서면 continue 처리
                if(nextX < 0 || nextY < 0 || nextX >= n || nextY >= m || 
                   maps[nextX][nextY] == 0 || visited[nextX][nextY]) {
                    continue; 
                } else { 
                    
                    queue.offer(new Position(nextX , nextY)); 
                    visited[nextX][nextY] = true;  //와 이게 되네???? 
                    maps[nextX][nextY] = maps[nowX][nowY] + 1 ; 
                }
            }
        }

        return maps[n-1][m-1] == 1 ? -1 : maps[n-1][m-1];
    }
}

class Position {
    private int x ; 
    private int y ; 
    
    public Position(int x , int y) {
        this.x = x; 
        this.y = y; 
    }
    
    public int getX() {
        return this.x; 
    }
    public int getY() {
        return this.y ; 
    }
}

코드설명

실패한 코드와 다른 점은 updatedMap을 없애고 기존 maps 에 데이터를 업데이트 했다.
하지만 이게 효율성에 영향을 주지는 않았고 방문 처리를 큐에 offer 라는 순간 효율성이 성공했다.

출력 결과

새롭게 알게된 점

(1) Queue의 add 와 offer의 차이

add는 큐가 가득 차서 삽입에 실패할 경우 IllegalStateException을 던져준다.
offer는 큐가 가득 차서 삽입에 실패할 경우 false를 반환한다.
성능 면에서는 차이가 없고 예외 처리를 어떻게 할 것이냐에 따라 달리 사용한다.

(2) 방문처리 순서에 따른 효율성 차이

첫번째 코드의 경우에는 같은 코드가 여러번 큐에 중복 저장될 수 있다.
두번째 코드는 새로운 위치를 방문처리하고 큐에 추가하므로 같은 위치가 중복 저장되지 않는다.

다음에 풀어볼 문제 - Deepest Leaves Sum

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

<성공코드>