[백준] 16946 - 벽 부수고 이동하기 4 (자바 Java)

[Gold II] 벽 부수고 이동하기 4 - 16946

문제 링크

성능 요약

메모리: 84284 KB, 시간: 656 ms

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

 

---

풀이

처음에는 벽이 있는 곳에서 모두 bfs를 돌렸는데 시간초과가 났다

 

두 번째 테스트 케이스

4 5
11001
00111
01010
10101

와 같은 경우에 0이 이어져있는 부분을 중복해서 방문하기 때문에 연산이 낭비되고 있기 때문이다.

 

그래서 0인 경우에 이동할 수 있는 블럭의 개수를 한 번의 bfs로 세었다.

그리고 result 배열에 각 개수를 저장하였다.

 

이 cnt를 같은 분리집합(이동 가능한 경우)에 있는 값에 모두 저장하기 위해 bfs를 수행하고, 지나온 경로들을 다시 큐에 저장해서 result 값을 업데이트하였다.

static void bfs(int r, int c, int cnt) {

    Queue<int[]> q = new LinkedList<>();
    Queue<int[]> pick = new LinkedList<>();
    q.add(new int[]{r, c});

    while (!q.isEmpty()) {
        int[] tmp = q.poll();
        int tr = tmp[0];
        int tc = tmp[1];
        if (visited[tr][tc] !=0) continue;
        visited[tr][tc] = cnt;
        pick.add(tmp);
        result[r][c]++; // 방문 가능한 곳
        for (int d = 0; d < 4; d++) {
            int nr = tr + dr[d];
            int nc = tc + dc[d];
            if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] != cnt && map[nr][nc] == 0)
                q.add(new int[]{nr, nc});
        }
    }
    int ans = result[r][c];
    
    // ans값 저장하기
    while (!pick.isEmpty()) {
        int[] tmp = pick.poll();
        int tr = tmp[0];
        int tc = tmp[1];
        result[tr][tc] = ans;
    }
}

 

그리고 답을 출력할 때는 map 값이 0인 경우에는 0, 1인 경우에는 사방 탐색을 통해 각 값의 합을 더하였다.

그런데 위에 말한 테스트 케이스 2의 경우 같은 분리집합에 속한 경우의 수는 한 번만 더해줘야 한다.

그래서 bfs를 돌 때 같은 분리 집합에 속한 경우는 visited 배열의 값을 모두 같게 지정해서 사방탐색의 index가 다른 index와 visited값이 같을 경우 해당 값은 더하지 않았다.

static int find(int r, int c) {
    if (map[r][c] == 0) return 0;

    // 네 방향을 조사하고 만약 특정 두 방향이 서로 연결 가능한 경우에는 중복 빼주기
    int ans = 1;

    label: for (int d = 0; d < 4; d++) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 0) {
            for (int j = 0; j < d; j++) {
                int checkr = r+dr[j];
                int checkc = c+dc[j];
                if (checkr >=0 && checkr< N && checkc>=0 && checkc< M && visited[nr][nc] == visited[checkr][checkc])
                    continue label;
            }
            ans+=result[nr][nc];
        }
    }
    return ans;
}

 

전체 코드

package BOJ.Gold.g2;

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

public class BOJ_16946_벽부수고이동하기4 {

    static int N, M;
    static int[][] map;
    static int[][] result;

    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};

    static int[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        result = new int[N][M];
        visited = new int[N][M];
        for (int i = 0; i < N; i++) {
            String input = br.readLine();
            for (int j = 0; j < M; j++)
                map[i][j] = input.charAt(j) - '0';
        }
        int cnt = 1;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0 && visited[i][j]==0)
                    bfs(i, j, cnt++);
            }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++)
                sb.append(find(i, j)%10); // 10으로 나눈 나머지인거 주의하기
            sb.append("\n");
        }
        System.out.print(sb);

    }

    static void bfs(int r, int c, int cnt) {

        Queue<int[]> q = new LinkedList<>();
        Queue<int[]> pick = new LinkedList<>();
        q.add(new int[]{r, c});

        while (!q.isEmpty()) {
            int[] tmp = q.poll();
            int tr = tmp[0];
            int tc = tmp[1];
            if (visited[tr][tc] !=0) continue;
            visited[tr][tc] = cnt;
            pick.add(tmp);
            result[r][c]++; // 방문 가능한 곳
            for (int d = 0; d < 4; d++) {
                int nr = tr + dr[d];
                int nc = tc + dc[d];
                if (nr >= 0 && nr < N && nc >= 0 && nc < M && visited[nr][nc] != cnt && map[nr][nc] == 0)
                    q.add(new int[]{nr, nc});
            }
        }
        int ans = result[r][c];

        // ans값 저장하기
        while (!pick.isEmpty()) {
            int[] tmp = pick.poll();
            int tr = tmp[0];
            int tc = tmp[1];
            result[tr][tc] = ans;
        }
    }

    static int find(int r, int c) {
        if (map[r][c] == 0) return 0;

        // 네 방향을 조사하고 만약 특정 두 방향이 서로 연결 가능한 경우에는 중복 빼주기
        int ans = 1;

        label: for (int d = 0; d < 4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr >= 0 && nr < N && nc >= 0 && nc < M && map[nr][nc] == 0) {
                for (int j = 0; j < d; j++) {
                    int checkr = r+dr[j];
                    int checkc = c+dc[j];
                    if (checkr >=0 && checkr< N && checkc>=0 && checkc< M && visited[nr][nc] == visited[checkr][checkc])
                        continue label;
                }
                ans+=result[nr][nc];
            }
        }
        return ans;
    }
}