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

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

1012번: 유기농 배추

풀이

대표적인 dfs와 bfs 알고리즘 문제 중 하나이다. 

필자는 재귀함수를 이용한 dfs가 제일 편하고 익숙해서 이걸로 해결했다.

 

1. N x M 크기의 int형 배열 2개를 만들어준다. 배추밭(map)과 방문 여부(check)를 기록할 배열이다.

2. 모든 배추밭을 다 돌면서 방문하지않은 곳의 인접한 배추를 찾으면 된다.

if (x < map.length-1 && map[x+1][y] == 1 && check[x+1][y] == 0) {
    dfs(x+1, y);
}
		
if (x > 0 && map[x-1][y] == 1 && check[x-1][y] == 0) {
    dfs(x-1, y);
}
		
if (y < map[x].length-1 && map[x][y+1] == 1 && check[x][y+1] == 0) {
    dfs(x, y+1);
}
		
if (y > 0 && map[x][y-1] == 1 && check[x][y-1] == 0) {
    dfs(x, y-1);
}

x축과 y축을 +, - 하면서 배열의 크기가 벗어나지않도록 해주기만 하면 쉽게 해결할 수 있다.

 

<최종코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[][] map;   // 지도 (배추밭)
    static int[][] check; // 방문여부
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
        int testCase = Integer.parseInt(br.readLine());
		
        StringTokenizer st;
        for (int i=0; i<testCase; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int N = Integer.parseInt(st.nextToken()); // x축
            int M = Integer.parseInt(st.nextToken()); // y축
            int K = Integer.parseInt(st.nextToken()); // 배추 개수
			
            map = new int[N][M];
            check = new int[N][M];
			
            for (int j=0; j<K; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = 1;
            }
			
            int cnt = 0;
			
            // 배추가 있고 방문하지 않은 곳인 경우 배추흰지렁이 추가
            for (int n=0; n<N; n++) {
                for (int m=0; m<M; m++) {
                    if (map[n][m] == 1 && check[n][m] == 0) {
                        cnt++;
                        dfs(n,m);
                    }
                }
            }
			
            System.out.println(cnt);
        }
    }
	
    public static void dfs(int x, int y) {
        check[x][y] = 1; // 방문 여부 체크
		
        if (x < map.length-1 && map[x+1][y] == 1 && check[x+1][y] == 0) {
            dfs(x+1, y);
        }
		
        if (x > 0 && map[x-1][y] == 1 && check[x-1][y] == 0) {
            dfs(x-1, y);
        }
		
        if (y < map[x].length-1 && map[x][y+1] == 1 && check[x][y+1] == 0) {
            dfs(x, y+1);
        }
		
        if (y > 0 && map[x][y-1] == 1 && check[x][y-1] == 0) {
            dfs(x, y-1);
        }
    }
}