문제 바로가기

정답코드

import java.io.*;
import java.util.*;

class Solution {
    
    static class Node{
        int x,y,sum;
        public Node(int x,int y,int sum){
            this.x=x;
            this.y=y;
            this.sum=sum;
        }
    }
    static int[] dx={0,0,1,-1};
    static int[] dy={1,-1,0,0};
    
    public int solution(int[][] maps) {        
        return bfs(maps);
    }
    
    static int bfs(int[][] maps){
        Queue<Node> q=new LinkedList<>();
        q.offer(new Node(0,0,0));
        boolean[][] visited=new boolean[maps.length][maps[0].length];
        visited[0][0]=true;
        
        while(!q.isEmpty()){
            Node cur=q.poll();
            int x=cur.x;
            int y=cur.y;
            int sum=cur.sum+1;
            
            if(x==maps.length-1 && y==maps[0].length-1){
                return sum;
            }
            
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                
                if(isEdge(nx,ny,maps) || visited[nx][ny] || maps[nx][ny]==0) continue;
                
                q.offer(new Node(nx,ny,sum));
                visited[nx][ny]=true;
                // System.out.println(nx+", "+ny+", "+sum);
            }
        }
        
        return -1;
    }
    
    static boolean isEdge(int x,int y, int[][] maps){
        return (x<0 || y<0 || x>=maps.length || y>=maps[0].length);
    }
}

회고

문제를 보자마자 어떻게 풀어야하는지 떠올랐지만 sum+1 처리에서 q.offer부분에서 해주니 틀려서 q.poll부분에서 해주었더니 맞았다.
기본적인 클래스, 큐, bfs 사용 문제였다.