Baekjoon 1012 유기농 배추

문제 이해

Baekjoon 1012 유기농 배추

배추밭에 벌레를 하나씩 놓는데, 벌레는 인접한 배추에 옮겨갈 수 있다. 모든 배추밭에 벌레를 번식시킨다고 했을 때 벌레가 최소 몇 마리 필요한지 구해야 한다.

배추밭으로 2차원 평면이 주어지고, 배추가 심어진 좌표가 주어진다.

임의 좌표 배추의 상 하 좌 우 좌표에 인접한 배추가 있다면 하나의 배추 그룹으로 보고, 전체 배추 그룹의 개수를 구하면 된다.

입출력 조건 확인

배추밭의 가로와 세로 길이가 50까지만 주어진다.
= 250

전체 index에 대해 한 번씩 확인하고 배추로 표시된 좌표에 도달하면 인접 배추를 찾는 반복문을 시행한다.
배추가 없는 경우 = O(n)
배추밭에 한 칸 간격으로 배추가 있는 경우 = O(4n)

Go

문제 풀이 내용 정리

1. 맵 그리기
   맵은 전역으로 선언하고 크기를 입력받아서 초기화(0) 해줬다.

2. 초기 배추 위치 표시
   배추의 위치를 입력받아 배추의 위치에 1로 표시를 했다.

3. 인접한 배추를 찾는 메소드 실행
   0, 0부터 시작해서 탐색을 하지 않은 배추(1)를 찾는다.
   좌표에 탐색을 하지 않은 배추(1)가 있다면 배추 그룹 횟수(count)를 1 증가시키고 해당 좌표로 인접한 배추를 찾는 메소드를 실행한다.
   만약 탐색을 하지 않은 배추(1)가 있다면 해당 배추를 탐색이 완료된 배추(2)로 표시하고 주변(상하좌우)에 탐색을 하지 않은 배추(1)가 있는지 확인한다.
   탐색을 하지 않은 배추(1)가 있다면 그 배추의 좌표로 메소드를 다시 호출한다.

Java

Baekjoon Source

import java.util.Scanner;

public class Main {
    static int[][] map;
    static int[] dX = {1, -1, 0, 0};
    static int[] dY = {0, 0, 1, -1};
    
    public static void bugGeneration(int[] point) {
        int searchX = point[0];
        int searchY = point[1];
        if (map[searchX][searchY] == 1)
            map[searchX][searchY] = 2;
        
        for (int i = 0; i < 4; i++) {
            int[] tmp = {point[0] + dX[i], point[1] + dY[i]};

            if (tmp[0] < 0 || tmp[0] >= map.length || tmp[1] < 0 || tmp[1] >= map[0].length)
                continue;
            else if (map[tmp[0]][tmp[1]] == 1)
                bugGeneration(tmp);
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int testCase = Integer.parseInt(sc.nextLine());

        for (int i = 0; i < testCase; i++) {
            String[] tmp = sc.nextLine().split(" ");
            int mapX = Integer.parseInt(tmp[0]);
            int mapY = Integer.parseInt(tmp[1]);
            int count = 0;
            map = new int[mapX][mapY];

            for (int j = 0; j < Integer.parseInt(tmp[2]); j++) {
                String[] bechu = sc.nextLine().split(" ");
                map[Integer.parseInt(bechu[0])][Integer.parseInt(bechu[1])] = 1;
            }
            
            for (int j = 0; j < map.length; j++) {
                for (int k = 0; k < map[0].length; k++) {
                    int[] point = {j, k};
                    if (map[j][k] == 1) {
                        count++;
                        bugGeneration(point);
                    }
                }
            }
            
            System.out.println(count);   
        }
    }
}

코드 문제점 및 해결 방법

이 간단한 문제에 396ms가 걸리는 것을 보면 Java의 위엄을 알 수 있는 것 같다.
(가상머신 시간 이슈 + Scanner 이슈)

아직까지 Scanner로 버티고 있는데 언제까지 버틸 수 있을까…