Jungol[1462] - 보물섬

링크

JUNGOL | 보물섬 > 문제은행

문제설명

• BFS STEP계산

문제풀이

• 매 칸에서 BFS STEP MAX 갱신

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;


public class Main1462 {
    public static LinkedList<int[]> q = new LinkedList<>();
    public static void DFS(int[] rc) {
        int temp=0;
        q.add(new int[] {rc[0],rc[1]});
        visit[rc[0]][rc[1]]=true;
        int[] now;
        int qsize;
        int nr=0;
        int nc=0;
        while(!q.isEmpty()) {
            qsize=q.size();
            for (int i = 0; i < qsize; i++) {
                now = q.poll();
                for (int d = 0; d < 4; d++) {
                    nr=now[0]+dir[d][0];
                    nc=now[1]+dir[d][1];
//                    경계 안에서 다음칸이 이동가능하며, 방문안한 칸인 경우 탐색
                    if(nr>=0 && nr<R && nc>=0 && nc<C && map[nr][nc]=='L' && !visit[nr][nc]) {
                        q.add(new int[] {nr,nc});
                        visit[nr][nc]=true;
                    }
                }
            }
            temp++;
        }
        Ans=Math.max(Ans, temp);
    }
    public static int[][] dir= {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };
    public static int R;
    public static int C;
    public static char[][] map;
    public static int Ans=0;
    public static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/jungol/1462.txt"));
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        map = new char[R][C];

        for (int i = 0; i < R; i++) {
            map[i]=br.readLine().toCharArray();
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if(map[i][j]=='L') {
                    visit = new boolean[R][C];
                    DFS(new int[] {i,j});
                }
            }
        }

        System.out.println(Ans-1);
    }
}

아쉬운점

• 전역변수 설정하고 로컬로 받아서 연산 안됬었음.

잘한점

• BFS STEP 계산