1012번:유기농배추

---

package dfs.Day250302;

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

public class Day01_유기농배추 {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] square;
    static boolean[][] visited;
    static int w; // 너비
    static int l; // 높이
    static int k; // 배추 개수
    static int cnt = 1;

    public static void dfs(int x, int y) {
        visited[y][x] = true;

        for (int i = 0; i < 4; i++) {
            int xx = dx[i] + x;
            int yy = dy[i] + y;

            if (xx >= 0 && yy >= 0 && xx < w && yy < l && !visited[yy][xx] && square[yy][xx] == 1) {
                visited[yy][xx] = true;
                cnt++;
                dfs(xx, yy);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        int[] result = new int[T];

        // 테스트 케이스 만큼 반복
        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken()); // 가로
            l = Integer.parseInt(st.nextToken()); // 세로
            k = Integer.parseInt(st.nextToken()); // 심어져 있는 배추의 개수
            square = new int[l][w];
            visited = new boolean[l][w];
            List<Integer> resultList = new ArrayList<>();

            // 배추 개수 받음
            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                square[y][x] = 1;
            }

            // 밭을 돈다.
            for (int j = 0; j < l; j++) {
                for (int m = 0; m < w; m++) {
                    if (square[j][m] == 1 && !visited[j][m]) {
                        dfs(m, j);
                        resultList.add(cnt);
                        cnt = 1;
                    }
                }
            }

            result[i] = resultList.size();
        }

        for (int i : result) {
            System.out.println(i);
        }
    }
}

문제

오늘은 유기농 배추에 대해서 풀었습니다.
2667번:단지번호붙이기 와 비슷한 문제입니다. 2667번을 풀었다면 충분히 혼자서 풀 문제였습니다.

유기농 농사를 위해 배추흰지렁이의 개수를 구하는 문제입니다. 지렁이는 근접한 배추에 접근할 수 있습니다.
(대각선은 접근하지 못합니다.)

다음 그림을 보면 이렇게 지렁이는 대각선 빼고 인근 배추에는 접근할 수 있으니 지렁이가 움직일 수 있는 구역은 총 5개입니다.
그럼 지렁이를 5마리를 구매 해야됩니다.

조건

static int[] dx = {-1, 1, 0, 0};
static int[] dy = {0, 0, -1, 1};
....

public static void dfs(int x, int y) {
	visited[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int xx = dx[i] + x;
		int yy = dy[i] + y;

		if (xx >= 0 && yy >= 0 && xx < w && yy < l && !visited[yy][xx] && square[yy][xx] == 1) {
			visited[yy][xx] = true;
			cnt++;
			dfs(xx, yy);
		}
	}
}

핵심 로직입니다. for문을 4번 도는 이유는 상하좌우를 돌면서 배추를 찾습니다.

int xx = dx[i] + x;
int yy = dy[i] + y;

를 통해 4개의 방향을 설정합니다. 그러나 초기 위치인 {0, 0}에서 왼쪽 또는 위로 이동할 경우 값이 없기 때문에 xx >= 0 && yy >= 0 조건을 통해 -1이 나오는 경우를 방지합니다.

또한, xx < w && yy < l 조건은 너비와 높이를 초과하지 않도록 설정했습니다.
마지막으로, !visited[yy][xx] && square[yy][xx] == 1 조건은 이미 방문한 곳은 건너뛰고, 값이 1인 경우에만 DFS 순환을 진행하도록 합니다.

결과

코테를 공부하면서 처음으로 아무것도 검색하지 않고 혼자서 푼 문제입니다.
다만, 좀 아쉬웠던 부분은 2차원 배열을 순회하고 선언하는 부분에서 조금 버벅였습니다.
예를 들어 이중 for문을 돌리다가 A[i][j]로 선언해야되는데 실수로 반대로 A[j][i]로 받거나 자잘한 실수가 있었습니다.