[백준] 1012번: 유기농 배추 - Java

💬 문제 파악하기

문제 출처

서로 연결되어 있는 구역의 개수를 찾는 문제입니다.
보자마자 바로 BFS와 DFS를 떠오르는 문제!

🔥 BFS 사용 - 메모리 초과

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

public class Main {
    static int testCases, width, height, K;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        StringTokenizer st;
        
        for(int i=0; i<testCases; i++) {
            st = new StringTokenizer(br.readLine());
            width = Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[width][height];
            visited = new boolean[width][height];
            
            for(int j=0; j<K; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }
            // 초기화 작업 끝
            
            int answer = 0;
            for(int j=0; j<width; j++) {
                for(int k=0; k<height; k++) {
                    if(map[j][k] == 1 && !visited[j][k]) {
                        bfs(j, k); 
                        // 탐색이 끝나고 돌아오면 하나의 구역 탐색이 이루어진 것이므로 answer 값을 1 증가시킨다.
                        answer++;
                    }
                }
            }
            System.out.println(answer);
        }
        
        br.close();
    }
    
    static void bfs(int x, int y) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x, y));
        
        while(!queue.isEmpty()) {
            Node now = queue.poll();
            visited[now.x][now.y] = true; 🔥🔥🔥🔥🔥
            
            for(int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                
                if(nx>=width || ny>=height || nx<0 || ny<0) continue;
                if(visited[nx][ny] || map[nx][ny] != 1) continue;
                
                queue.add(new Node(nx, ny));
            }  
        }
    }
    
    static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

BFS를 사용해 문제를 풀 때에는 메모리 초과에 주의하여야 합니다.

Queue에 Node를 넣은 뒤 꺼낼 때 방문 체크를 하게 되면 중복된 값이 들어갈 수 있기 때문에 Queue에 Node를 넣은 뒤 바로 방문 체크를 해주어야 합니다! (아래 정답 코드)

⭐️ BFS 사용 - 정답

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

public class Main {
    static int testCases, width, height, K;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        StringTokenizer st;
        
        for(int i=0; i<testCases; i++) {
            st = new StringTokenizer(br.readLine());
            width = Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[width][height];
            visited = new boolean[width][height];
            
            for(int j=0; j<K; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }
            
            int answer = 0;
            for(int j=0; j<width; j++) {
                for(int k=0; k<height; k++) {
                    if(map[j][k] == 1 && !visited[j][k]) {
                        bfs(j, k);
                        answer++;
                    }
                }
            }
            System.out.println(answer);
        }
        
        br.close();
    }
    
    static void bfs(int x, int y) {
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(x, y));
        visited[x][y] = true;
        
        while(!queue.isEmpty()) {
            Node now = queue.poll();
            
            for(int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                
                if(nx>=width || ny>=height || nx<0 || ny<0) continue;
                if(visited[nx][ny] || map[nx][ny] != 1) continue;
                
                queue.add(new Node(nx, ny));
                visited[nx][ny] = true;
            }  
        }
    }
    
    static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

⭐️ DFS 사용 - 정답

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

public class Main {
    static int testCases, width, height, K;
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCases = Integer.parseInt(br.readLine());
        StringTokenizer st;
        
        for(int i=0; i<testCases; i++) {
            st = new StringTokenizer(br.readLine());
            width = Integer.parseInt(st.nextToken());
            height = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[width][height];
            visited = new boolean[width][height];
            
            for(int j=0; j<K; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }
            
            int answer = 0;
            for(int j=0; j<width; j++) {
                for(int k=0; k<height; k++) {
                    if(map[j][k] == 1 && !visited[j][k]) {
                        dfs(j, k);
                        answer++;
                    }
                }
            }
            System.out.println(answer);
        }
        
        br.close();
    }
   
    
    static void dfs(int x, int y) {
        if(visited[x][y]) return;
        
        visited[x][y] = true;
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
                
            if(nx>=width || ny>=height || nx<0 || ny<0) continue;
            if(visited[nx][ny] || map[nx][ny] != 1) continue;
            
            dfs(nx, ny);
        }
    }
    
    static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}