백준(Java)

[Java] 백준 1012번 (유기농 배추) [실버2]

준코메 2025. 2. 24. 22:27

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

이 문제로 그래프 탐색을 처음 접했는데 처음에는 어떻게 접근해야 할지 몰라서 풀지 못했다..

 

코딩 초보인 주제에 혼자서 풀어보겠다고 몇 시간씩 고민하며 생각했는데.. 1시간 정도 해보고 안되면 더 붙잡아선 안 될 것 같다.

 

요즘은 Chat-GPT가 있어서 막히는 문제가 생길때 문제 접근 방법을 물어볼 수 있어서 좋은 것 같다.

 

결국 다양한 유형의 문제를 많이 풀어보고 각 문제 유형별 정해진 접근법을 익히는게 중요한 것 같다.

 

물론 창의력과 사고력을 기르기 위해서는 혼자서 접근 방법을 찾아나가야 한다는 말도 맞지만, 그 말도 이미 유형별 기본적인 풀이 방법은 전부 알고 있는 플레티넘이나 다이아 이상이라는 전제에서나 맞는 말인 것 같다..

 

이 문제는 배추가 심어진 곳을 순차로 탐색하면서 각 탐색 지점으로부터 상하좌우 방향으로 확장해서 탐색하는 문제이다.

 

그리고 한 번 방문한 지점은 방문 표시를 해둬서 중복 방문을 하지 않도록 한다.

 

정답

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        for (int a = 0; a<T; a++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            int[][] filed = new int[M][N];
            boolean[][] visited = new boolean[M][N];
            List<int[]> cabbageList = new ArrayList<>();
    
            for (int i=0; i<K; i++) {
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
    
                filed[X][Y] = 1; // 배추가 심어진 걸 표시
                
                cabbageList.add(new int[]{X, Y}); // 배추 위치를 담은 리스트
            }

            int area = 0;

            // 상하좌우 좌표
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};
    
            for (int[] p : cabbageList) {

                int startX = p[0];
                int startY = p[1];
                
                if (visited[startX][startY] == false) { // 방문하지 않았으면 탐색 시작
                    area += 1;
                    Queue<int[]> queue = new LinkedList<>(); // 같은 영역의 배추 좌표를 담을 큐
                    queue.add(new int[] {startX, startY}); // 큐에 담고
                    visited[startX][startY] = true; // 방문 표시

                    while (queue.size() != 0) { // 큐에 좌표가 담겨 있을 때 실행

                        int[] pollArr = queue.poll();
                        int x = pollArr[0];
                        int y = pollArr[1];

                        for (int i=0; i<4; i++) { // 4회 반복
                            int nx = x + dx[i];
                            int ny = y + dy[i];
                            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                                if (filed[nx][ny] == 1 && visited[nx][ny] == false) { // 배추가 있으면서 탐색 안했으면
                                    queue.add(new int[] {nx, ny}); // 큐에 담기
                                    visited[nx][ny] = true;
                                }
                            }
                        }
                    }
                }
            }
            bw.write(area + "\n");
        }
        bw.flush();
        bw.close();
    }
}

 

풀이

1. 배추밭을 나타낼 filed, 방문 여부를 나타낼 visited, 배추의 위치만을 담을 cabbageList를 생성한다.

            int[][] filed = new int[M][N]; // 배추밭
            boolean[][] visited = new boolean[M][N]; // 방문 여부
            List<int[]> cabbageList = new ArrayList<>(); // 배추 심어진 곳

 

2. 이후 K개의 배추 위치를 각각 filed 배열에 표시하고, cabbageList 리스트에 담는다.

            for (int i=0; i<K; i++) {
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());

                filed[X][Y] = 1; // 배추가 심어진 걸 표시

                cabbageList.add(new int[]{X, Y}); // 배추 위치를 담은 리스트
            }

이렇게 하면 filed에는 위와 같은 2차원 배열로 0과 1의 숫자가 담길거고, cabbageList에는 1의 좌표값만 담길 것이다.

 

3. 배추 영역의 개수를 표시할 area와 상하좌우 좌표를 나타낼 dx, dy를 선언한다.

            int area = 0;

            // 상하좌우 좌표
            int[] dx = {0, 0, 1, -1};
            int[] dy = {1, -1, 0, 0};

 

4. cabbageList에서 좌표값을 하나 뺐을 때, 그 좌표가 방문하지 않은 곳이라면, 그 좌표를 큐에 넣고 방문 표시를 한 뒤, 탐색을 시작한다.

            for (int[] p : cabbageList) {

                int startX = p[0];
                int startY = p[1];

                if (visited[startX][startY] == false) { // 방문하지 않았으면 탐색 시작
                    area += 1;
                    Queue<int[]> queue = new LinkedList<>(); // 같은 영역의 배추 좌표를 담을 큐
                    queue.add(new int[] {startX, startY}); // 큐에 담고
                    visited[startX][startY] = true; // 방문 표시

 

5. 탐색 시작 좌표를 중심으로 상하좌우를 탐색했을 때 배추가 존재하면서 방문하지 않은 곳이면 그 새로운 좌표를 큐에 넣고 방문 표시를 해준다.

 

만약 배추는 존재하는데 이미 방문한 곳이라면 큐에 넣지 않는다.

 

이렇게 해주는 이유는 이미 방문한 좌표는 재탐색을 할 필요가 없기 때문이다.

 

예를 들어 (0, 0)을 중심으로 상하좌우를 탐색했을 때 (0, 1)을 탐색했지만, 다음번에 (1, 1)을 중심으로 상하좌우를 탐색했을 때 다시 (0, 1)이 재탐색되기 때문에 시간 낭비가 된다.

 

또한, 새로운 탐색 좌표인 nx와 ny가 배추밭 영역을 넘어서지 않도록 if (nx >= 0 && ny >= 0 && nx < M && ny < N)를 통해 배추밭 영역 내의 좌표인지 확인해준다.

                    while (queue.size() != 0) { // 큐에 좌표가 담겨 있을 때 실행

                        int[] pollArr = queue.poll();
                        int x = pollArr[0];
                        int y = pollArr[1];

                        for (int i=0; i<4; i++) { // 4회 반복
                            int nx = x + dx[i];
                            int ny = y + dy[i];
                            if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
                                if (filed[nx][ny] == 1 && visited[nx][ny] == false) { // 배추가 있으면서 탐색 안했으면
                                    queue.add(new int[] {nx, ny}); // 큐에 담기
                                    visited[nx][ny] = true;
                                }
                            }
                        }
                    }
                }
            }