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

[guswns1659]

문제 풀이 핵심 아이디어

• 시작점이 여러개인 기본 DFS 문제

어려운점 및 실수

• 행과 열을 반대로 주기 때문에 기본 로직도 행과 열을 잘 고려해서 짜야 한다.
• 가로를 먼저, 세로가 그 다음에 들어오기 때문에 아래 코드처럼 M(열)을 먼저 받아야 한다.
• dist의 값을 초기화할 때도 입력되는 좌표(ex. 0 2)가 가로(열)부터 들어오니까 반대로 초기화한다.

            M = Integer.parseInt(inputs[0]);
            N = Integer.parseInt(inputs[1]);
            int itemCount = Integer.parseInt(inputs[2]);

            dist = new int[N][M];

            // dist 초기화
            for (int count = 0; count < itemCount; count++) {
                String[] coords = br.readLine().split(" ");
                dist[Integer.parseInt(coords[1])][Integer.parseInt(coords[0])] = -1;
            }

• dfs 돌 때 배열의 크기를 벗어나는 조건을 잘 체크한다. N인지 M인지 등

            for (int index = 0; index < 4; index++) {
                int x2 = location[0] + dx[index];
                int y2 = location[1] + dy[index];

                if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= M) continue;
                if (dist[x2][y2] >= 0) continue;
                dist[x2][y2] = dist[location[0]][location[1]] + 1;

                q.offer(new int[]{x2, y2});
            }
        }

풀이

package backjun.bfs;

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

public class N1012 {

    static int[] dx = new int[]{1, -1, 0, 0};
    static int[] dy = new int[]{0, 0, 1, -1};
    static int[][] dist;
    static int N,M;

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

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

        for (int loop = 0; loop < testCase; loop++) {
            String[] inputs = br.readLine().split(" ");
            M = Integer.parseInt(inputs[0]);
            N = Integer.parseInt(inputs[1]);
            int itemCount = Integer.parseInt(inputs[2]);

            dist = new int[N][M];

            // dist 초기화
            for (int count = 0; count < itemCount; count++) {
                String[] coords = br.readLine().split(" ");
                dist[Integer.parseInt(coords[1])][Integer.parseInt(coords[0])] = -1;
            }

            int answer = 0;

            // 이중 for문 돌면서 시작점이 가능한 점 찾기
            for (int row = 0; row < N; row++) {
                for (int column = 0; column < M; column++) {
                    if (dist[row][column] == -1) {
                        dfs(row,column);
                        answer++;
                    }
                }
            }
            System.out.println(answer);
        }
    }

    public static int dfs(int row, int column) {
        Queue<int[]> q = new LinkedList<>();
        dist[row][column] = 0;
        q.offer(new int[]{row, column});
        int area = 0;

        while(!q.isEmpty()) {
            int[] location = q.poll();
            area++;

            for (int index = 0; index < 4; index++) {
                int x2 = location[0] + dx[index];
                int y2 = location[1] + dy[index];

                if (x2 < 0 || x2 >= N || y2 < 0 || y2 >= M) continue;
                if (dist[x2][y2] >= 0) continue;
                dist[x2][y2] = dist[location[0]][location[1]] + 1;

                q.offer(new int[]{x2, y2});
            }
        }
        return area;
    }
}