백준 2636 치즈 with 자바

---

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

풀이

테두리(0,0)에서부터 2차원 배열을 치즈가 다 없어질 때까지 반복적으로 전체 탐색하면 된다

탐색할 때는 4방향 탐색을 하여

치즈가 있는 경우는 해당 위치를 기억하고

탐색이 다 끝나면

해당 위치의 치즈를 삭제해 주면 된다

 

전역 변수를 선언해 주고

static int N;
static int M;
static boolean[][] arr;				// 2차원 배열
static int totalCount;				// 전체 치즈 개수
static int[] di = {-1, 1, 0, 0};	// 4방향 탐색에 쓰일 행 인덱스
static int[] dj = {0, 0, 1, -1};	// 4방향 탐색에 쓰일 열 인덱스
static boolean[][] visited;			// bfs에 사용할 방문표시
static LinkedList<Node> meltList;	// 녹일 치즈의 위치
static int lastCount;				// 녹기 전에 남아 있는 치즈 조각

 

녹일 치즈의 위치를 저장할 Node 클래스를 만들어 준다

간단하게 배열의 인덱스 정보를 담고 있다

private static class Node {
    int i;
    int j;

    public Node(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

 

입력을 받으면서

치즈인 경우 2차원 배열에 표시를 하고

전체 치즈 개수를 +1 해준다

if (n == 1) {
    arr[i][j] = true;
    totalCount++;
}

 

전체 치즈 개수가 0이 될 때까지

테두리에서 bfs를 계속 돌려준다

bfs를 돌리기 전, 남아 있는 치즈 개수 lastCount를 업데이트해주고

치즈 녹이기가 끝나면 시간을 +1 해준다

int time = 0;

while (totalCount != 0) {
    lastCount = totalCount;
    visited = new boolean[N][M];
    meltList = new LinkedList();

    bfs(0, 0);

    melt();
    time++;
}

 

---

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N;
    static int M;
    static boolean[][] arr;
    static int totalCount;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, 1, -1};
    static boolean[][] visited;
    static LinkedList<Node> meltList;
    static int lastCount;

    private static class Node {
        int i;
        int j;

        public Node(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

	// 2차원 배열을 벗어나지 않는지 확인
    static boolean isIn(int i, int j) {
        if (i >= 0 && i < N && j >= 0 && j < M) return true;
        return false;
    }

	// bfs를 돌면서 녹일 치즈의 위치를 저장
    static void bfs(int i, int j) {
        Queue<Node> queue = new LinkedList();
        queue.add(new Node(i, j));
        visited[i][j] = true;

        while (!queue.isEmpty()) {
            Node node = queue.poll();
            i = node.i;
            j = node.j;
            for (int dir = 0; dir < 4; dir++) {
                int newI = i + di[dir];
                int newJ = j + dj[dir];

                if (isIn(newI, newJ) && !visited[newI][newJ]) {
                    visited[newI][newJ] = true;
                    Node newNode = new Node(newI, newJ);

					// 테두리 주위에 있는 치즈를 녹이기 위해
                    // 해당 치즈의 위치를 저장
                    if (arr[newI][newJ]) {
                        meltList.add(newNode);
                    } else {
                        queue.add(newNode);
                    }
                }
            }
        }
    }

	// 치즈를 녹이는 작업
    private static void melt() {
        while (!meltList.isEmpty()) {
            Node node = meltList.poll();
            arr[node.i][node.j] = false;
            totalCount--;
        }
    }


    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        totalCount = 0;

        arr = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int n = Integer.parseInt(st.nextToken());

                if (n == 1) {
                    arr[i][j] = true;
                    totalCount++;
                }
            }
        }

        int time = 0;

        while (totalCount != 0) {
            lastCount = totalCount;
            visited = new boolean[N][M];
            meltList = new LinkedList();

            bfs(0, 0);

            melt();
            time++;
        }

        System.out.println(time + "\n" + lastCount);
    }
}

 

탐색 범위 줄이기

테두리에서부터 bfs를 시작하면 모든 테두리를 탐색해야 한다

어차피 테두리에는 치즈가 없으므로, 테두리를 탐색하지 않아도 결과에는 영향을 미치지 않는다

그래서 테두리 안쪽만을 탐색하도록 탐색 범위를 줄여보았다

while (totalCount != 0) {
    lastCount = totalCount;
    visited = new boolean[N][M];
    meltList = new LinkedList();

    for (int j = 0; j < M; j++) {
        if (!visited[0][j]) {
            bfs(0, j);
        }
    }

    for (int i = 0; i < N && M - 1 > 0; i++) {
        if (!visited[i][M - 1]) {
            bfs(i, M - 1);
        }
    }

    for (int j = 0; j < M && N - 1 > 0; j++) {
        if (!visited[N - 1][0]) {
            bfs(N - 1, 0);
        }
    }

    for (int i = 0; i < N; i++) {
        if (!visited[i][0]) {
            bfs(i, 0);
        }
    }

    melt();
    time++;
}

결과는 12ms 시간 단축이 되었다