[백준] 1743번 음식물 피하기 - Java, 자바

난이도

실버 1

문제

https://www.acmicpc.net/problem/1743

풀이

DFS/BFS로 풀 수 있는 문제. 나는 BFS로 풀었다.

문제풀이
1. 음식물 쓰레기의 위치를 2차원 배열(arr)에 담는다. => arr[x-1][y-1] = 1
2. 2중 for문을 돌리며 arr[i][j]에 음식물이 있을 때, bfs(i,j)를 실행하고 최댓값인지 판단한다.
3. bfs

• (i,j)를 큐에 넣는다.
• arr[i][j]를 0으로 바꿔준다.(방문 표시)
• 큐가 비어있지 않을 때,
  • q.poll()
  • count++
  • 4방향으로 움직일 수 있는 for문 실행하고 움직인 위치에 음식물쓰레기가 있다면 그 위치를 0으로(방문표시) 바꿔주고 q.add를 한다.

코드

package 완전탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class boj_1743 {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int n, m;
    static int[][] arr;

    public static void main(String[] args) throws IOException {
        int max = Integer.MIN_VALUE;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        arr = new int[n][m];

        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[x - 1][y - 1] = 1;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1) {
                    max = Math.max(max, bfs(i, j));
                }
            }
        }
        System.out.println(max);

    }

    static int bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        int count = 0;
        q.add(new int[]{x, y});
        arr[x][y] = 0;
        while (!q.isEmpty()) {
            int[] dir = q.poll();
            int xx = dir[0];
            int yy = dir[1];
            count++;
            for (int i = 0; i < 4; i++) {
                int nx = xx + dx[i];
                int ny = yy + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (arr[nx][ny] == 1) {
                        arr[nx][ny] = 0;
                        q.add(new int[]{nx, ny});
                    }
                }
            }
        }
        return count++;
    }
}