[자바] 백준 5993 - Invasion of the Milkweed (java)

 문제 : boj5993

---

 

필요 알고리즘 개념

• 너비 우선 탐색 (bfs)
  
  • 기본적인 형태의 너비우선 탐색 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  BFS를 모른다면 이 글을 보자. 깁노적인 형태의 BFS 문제이므로 별다른 구현 풀이는 필요 없다. 주의점은 일반적인 문제와 다르게 입력이 가로, 세로 순서로 들어온다는 점과, Mx, My도 마찬가지로 가로, 세로 순서로 들어오고 좌측 아래부터 (1,1)이라는 점이다.

 

  즉, 입력 받은 순서대로 배열에 기입했다면 int sr = r - Integer.parseInt(st.nextToken()); 이런식으로 인덱스를 뒤로 보내줘야 한다(r은 문제에서 제시된 Y, sr은 My 이다.)

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int c = Integer.parseInt(st.nextToken());
        int r = Integer.parseInt(st.nextToken());
        int sc = Integer.parseInt(st.nextToken()) - 1;
        int sr = r - Integer.parseInt(st.nextToken());
        boolean[][] arr = new boolean[r][c];
        for (int i = 0; i < r; i++) {
            String row = br.readLine();
            for (int j = 0; j < c; j++) {
                arr[i][j] = row.charAt(j)=='*';
            }
        }

        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{sr, sc, 0});
        arr[sr][sc] = true;
        int answer = 0;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int cr = cur[0];
            int cc = cur[1];
            int cnt = cur[2];
            answer = cnt;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0) continue;
                    int nr = cr+dr;
                    int nc = cc+dc;
                    if (nr<0||nr>=r||nc<0||nc>=c||arr[nr][nc]) continue;
                    arr[nr][nc] = true;
                    q.add(new int[]{nr, nc, cnt+1});
                }
            }
        }
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}