백준 Q1012 - 유기농 배추

문제 및 입출력

---

풀이

바로 이전에 풀었던 단지번호 붙이기 문제와 동일한 유형의 문제이다.
문제에서 요구하는 약간의 차이는 두 가지가 있다.

1. 단지번호 붙이기 문제는 배열 전체를 입력받았고, 유기농 배추 문제는 배열에서 1인값의(배추흰지렁이) 위치, 즉 DFS를 실행해야하는 인덱스만 입력을 받은점
2. 단지 번호 붙이기 문제는 각 단지마다 아파트의 수를 구하기 위해 DFS 마다 count를 사용했지만, 유기농 배추 문제는 단지의 개수만 파악하면 되는점

static int[][] map;
static boolean[][] visited;
static int[] dx = {1, 0, -1, 0};
static int[] dy = {0, -1, 0, 1};
static int M, N, B;
static ArrayList<Integer> result = new ArrayList<>();

변수 설명

• map: 양배추 밭을 담을 배열
• dx,dy: 상하좌우를 탐색하기 위한 방향 벡터
• M,N,B: 가로 길이, 세로길이, 심어져 있는 배추의 개수

for (int i = 0; i < B; i++) {
	String[] str = br.readLine().split(" ");
	int x = Integer.parseInt(str[0]);
	int y = Integer.parseInt(str[1]);
	map[x][y] = 1;
}

문제에 주어졋듯이 배추흰지렁이의 위치를 입력받아 1로 초기화 하였다.

for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		if (map[i][j] == 1 && visited[i][j] == false) {
			visited[i][j] = true;
			dfs(i, j);
			count++;
			}
	}
}

현재 위치가 배추흰지렁이가 있는 위치이고, 방문하지 않았으면 한 번의 dfs를 진행한 이후 count 값을 올려준다
여기서 count는 배추흰지렁이가 몇개의 집합이 있는지 세기 위한 변수이다.

private static void dfs(int i, int j) {
	for (int k = 0; k < 4; k++) {
		int nextX = i + dx[k];
		int nextY = j + dy[k];
		if (nextX >= 0 && nextY >= 0 && nextX < M && nextY < N 
        		&& visited[nextX][nextY] == false && map[nextX][nextY] == 1) {
			visited[nextX][nextY] = true;
			dfs(nextX, nextY);
		}
	}
}

저번에 풀이했던 문제와 dfs 코드는 동일하므로 추가 설명을 안해도 될 것 같다.

---

최종 코드

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int M, N, B;
    static ArrayList<Integer> result = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken()); // 가로길이
            N = Integer.parseInt(st.nextToken()); // 세로길이
            B = Integer.parseInt(st.nextToken()); // 심어져 있는 배추의 개수

            map = new int[M][N];
            visited = new boolean[M][N];

            for (int i = 0; i < B; i++) {
                String[] str = br.readLine().split(" ");
                int x = Integer.parseInt(str[0]);
                int y = Integer.parseInt(str[1]);
                map[x][y] = 1;
            }

            int count = 0;
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == 1 && visited[i][j] == false) {
                        visited[i][j] = true;
                        dfs(i, j);
                        count++;
                    }
                }
            }
            result.add(count);
        }
        for (Integer i : result) {
            System.out.println(i);
        }
    }

    private static void dfs(int i, int j) {
        for (int k = 0; k < 4; k++) {
            int nextX = i + dx[k];
            int nextY = j + dy[k];
            if (nextX >= 0 && nextY >= 0 && nextX < M 
            		&& nextY < N && visited[nextX][nextY] == false
                    && map[nextX][nextY] == 1) {
                visited[nextX][nextY] = true;
                dfs(nextX, nextY);
            }
        }
    }
}

---

풀이 후기

그래프 + DFS를 몇 문제 풀다보니 생각보다 익숙해졌다. 이제 방향 벡터를 사용하여 푸는 문제는 능숙하게 풀 수 있을것 같고, 다른 유형의 DFS 문제를 접하기 위해 더 많은 문제를 풀어야 겠다.