[이취코] CH 08. 실전 문제 미로 탈출

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

본 게시글은 해당 책에 나와있는 문제를 풀고 기록한 것으로 해당 코드의 문제를 확인하고 싶다면 위의 링크를 통해 책을 구입한 후

책 ch0 152p를 참고하기를 바란다.

 

문제

CH 05. 실전 문제 미로 탈출

해당 문제는 백준의 https://www.acmicpc.net/problem/2178 해당 문제와 매우 유사하니 해당 문제를 참고하기를 바란다.

 

 

  문제접근 방법   

문제에서 최단거리를  구하라고 하였기 때문에 BFS를 통해서 문제를 접근하여 작성하였다.

< 초기 코드  >

import java.util.*;

public class Main{
    
    public static int maze[][];
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        maze=new int[n][m];
        visited=new boolean[n][m];
        
        for(int i=0;i<n;i++){
            String str=s.next();
            for(int j=0;j<m;j++){
                maze[i][j]=str.charAt(j)-'0';
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(!visited[i][j]&&maze[i][j]!=0){
                    bfs(i,j);
                }
            }
        }
        System.out.print(maze[n-1][m-1]);
        
    }
    
    public static void bfs(int x,int y){
        if(visited[x][y] ||maze[x][y]==0)return;
        Queue<Map.Entry<Integer,Integer>> queue=new LinkedList<>();
        queue.offer(new AbstractMap.SimpleEntry(x,y));
        visited[x][y]=true;
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        
        while(!queue.isEmpty()){
            Map.Entry<Integer,Integer> entry=queue.poll();
            int a=entry.getKey();
            int b=maze[x][y];
            for(int i=0;i<4;i++){
                int xx=dx[i]+x;
                int yy=dy[i]+y;
                if(xx>=0&&yy>=0&&yy<maze[0].length&&xx<maze.length){
                    
                    if(!visited[xx][yy]&&maze[xx][yy]!=0){
                        maze[xx][yy]+=b;
                        queue.offer(new AbstractMap.SimpleEntry(xx,yy));
                        visited[xx][yy]=true;
                    }
                }
                
            }
        }
        
        
        
    }
}

초기코드에 문제점은 bfs에 초기 매개변수인 x,y로 값을 고정해두고 변환한다에 있다. xx=dx[i]+x이런식으로 식이 변해야하는데 식이 변하지 않는 다는 문제점이 존재하였고 main함수에서 bfs를 반복문으로 쓸데없이 호출하는 연산이 존재하였다. 해당 문제점을 아래와 같이 수정하였다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    
    public static int maze[][];
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        maze=new int[n][m];
        visited=new boolean[n][m];
        
        for(int i=0;i<n;i++){
            String str=s.next();
            for(int j=0;j<m;j++){
                maze[i][j]=str.charAt(j)-'0';
            }
        }
        bfs(0, 0);
        System.out.print(maze[n-1][m-1]);
        
    }
    
    public static void bfs(int x,int y){
        if(visited[x][y] ||maze[x][y]==0)return;
        Queue<Map.Entry<Integer,Integer>> queue=new LinkedList<>();
        queue.offer(new AbstractMap.SimpleEntry(x,y));
        visited[x][y]=true;
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        
        while(!queue.isEmpty()){
            Map.Entry<Integer,Integer> entry=queue.poll();
            int a=entry.getKey();
            int b=entry.getValue();
            int c=maze[a][b];
            for(int i=0;i<4;i++){
                int xx=dx[i]+a;
                int yy=dy[i]+b;
                if(xx>=0&&yy>=0&&yy<maze[0].length&&xx<maze.length){
                    
                    if(!visited[xx][yy]&&maze[xx][yy]!=0){
                        maze[xx][yy]+=c;
                        queue.offer(new AbstractMap.SimpleEntry(xx,yy));
                        visited[xx][yy]=true;
                    }
                }
                
            }
        }
        
        
        
    }
}

해당 문제는 시작점부터 최단거리를 구하는 문제이기 때문에 dfs와 같이 반복문으로 접근할 필요가 없다. 또 x대신 a와 b를 수정하여 코드를 작성하였다.

 

  마무리  

해당 문제는 BFS를 이해하는데 굉장히 큰 도움이 되었다. 앞서 DFS관련 문제를 풀어서 보다 쉽게 접근이 가능했다.

 

  추가 코드 분석 및 풀이  

본인이 풀이한 방식말고 저자는 아래와 같이 접근한것을 확인하였다.

https://github.com/ndb796/python-for-coding-test/blob/master/5/11.java

python-for-coding-test/5/11.java at master · ndb796/python-for-coding-test

전체적인 로직은 같다.하지만 디테일에서 차이가 발생하는데 본인은 Queue에서 Map.Entry를 활용하여 2개의 값을 받아 저장하였지만 저자는 Node라는 별도의 클래스를 작성하여 활용한 것을 확인해볼수 있다.