[백준/JAVA] 1743번: 음식물 피하기

🔺 문제

1743번: 음식물 피하기

 

🔺 코드

import java.util.*;
import java.io.*;
public class Main {
    static int[] dx = {0, 0, -1, 1};    // 좌우
    static int[] dy = {1, -1, 0, 0};    // 상하
    
    static int N, M, K; // 세로, 가로, 음쓰 개수
    static int max;     // 가장 큰 음식물 크기
    static int cnt;
    
    static int[][]     map;
    static boolean[][] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        visited = new boolean[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());
            
            map[x - 1][y - 1] = 1;
        }
        
        // 각 점마다 BFS 수행
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(!visited[i][j] && map[i][j] != 0) {
                    cnt = 0;
                    BFS(i, j);
                    max = Math.max(max, cnt);
                }
            }
        }
        System.out.println(max);
    }
    
    static void BFS(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        
        visited[x][y] = true;
        cnt++;
        
        while(!queue.isEmpty()) {
            int[] now = queue.poll();
            
            // 상하좌우 탐색
            for(int d = 0 ; d < 4 ; d++) {
                int curX = now[0] + dx[d];
                int curY = now[1] + dy[d];
                
                if(curX < 0 || curX >= N || curY < 0 || curY >= M ) continue;
                if(!visited[curX][curY] && map[curX][curY] != 0) {
                    queue.add(new int[] {curX, curY});
                    visited[curX][curY] = true;
                    cnt++;
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ DFS / BFS
- 각 점마다 BFS 수행
- 이 때 cnt는 0으로 초기화한 상태에서 진행해야 각 점마다 cnt를 구할 수 이씀!
- 그리고 이 값과 max를 비교해서 더 큰 값을 결과로 저장

map 배열을 int배열로 안 하고 boolean 배열로 해도 됨!

 

---

🔺 다른 풀이들

- cnt를 BFS 메소드 안에 넣으셨다

& 방문 배열인 boolean[] visited를 만들지 않고, int[][] map에서 방문 가능한 위치(=1)일 때 값을 0으로 바꾸면서 한 번에 방문 처리하셨다

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

 

---

💬 느낀 점

이제 상하좌우 탐색 좀 감이 잡혔다!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준_1743 음식물 피하기(자바) / DFS & BFS