[백준 16946번] 벽 부수고 이동하기4(java)

문제

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

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

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

  입력

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

  출력

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

  

---

정답

지금까지 풀었던 코딩테스트 문제중에 제일 어려웠고 가장 오래 고민했다. 처음에는 당연히 BFS나 DFS로 전체를 탐색하는게 이중for문으로 탐색하는것보다 빠르다고 생각해, 탐색의 시작을 BFS로 하였다. 문제는 BFS나 DFS나 둘다 이중for문을 쓴다는 것이였고 충분히 시간초과가 나왔었다.
이 문제는 이동할 수 있는 길을 그룹핑 하는 것이 중요하다.
예제 입력2를 통해서 설명해보자

처음에 Map에는 1(벽)과 0(길) 로 이뤄진 배열을 만든다. 그리고 그룹아이디를 보관할 같은 크기의 배열groupIdmap을 만들고 groupId의 길이를 저장할 배열 lengthList를 생성한다.(처음에는 모두다 0으로 초기화 된다.)

• Map을 이중for문으로 돌면서 0을 만나면 BFS()를 실행한다.(DFS()로 해도 상관없다.
  BFS()의 조건은 주변 값이 0(길) 일때 계속해서 돌게 한다. BFS()가 돈 횟수가 그 길이 갈수있는 최대 길이 이다. 위 Map에서는 (0,3)값이 먼저 BFS()를 돌게 된다. BFS()를 다 돌면 배열의 값은 이렇게 변한다.
  

  

  
  Map(0,3)과 Map(0,4)는 같은 그룹에 속해 있으므로 같은 groupId값을 가지게 된다. lengthList에는 1의 갯수가 2개 이므로 인덱스 1 위치에 2값을 저장하다.
• 다시 이중 for문을 돌면서 한번도 만난적 없는 0을 찾아서 BFS()를 똑같이 실행한다.
  

  

  
  위의 그림처럼 배열의 값이 변하게 된다.
  이제 이중 for문을 끝까지 돌리면 아래의 상태가 된다.
  

  

이제 길의 그룹 id와 그 길의 최대길이를 다 알아냈다. 그럼 이제 map을 돌면서 1(벽)일때 주변에 있는 길들의 길이를 합치면 된다. 만약 합치는데 groupId가 중복되는 길이 있다면 합치면 안된다.(이 중복 때문에 길을 그룹핑 해주었다.)

사실 이 생각은 금방했지만 시간초과가 쉽게 뜨기 좋은 문제이다. 나도 또한 시간초과가 계속해서 떴고 고민을 엄청 오래하다가 백준 사이트에 질문을 하였다. 문제는 BFS()안에 배열 객체를 생성해주었기 때문이다. boolean [][] visited = new boolean[n][m];을 하게 해줬는데 BFS가 M번 호출되면 배열 생성시간O(n*m) * BFS()호출 횟수O(M) = O(n*m^2)가 나오게 된다.

이 문제로 시간 복잡도에 대한 새로운 눈이 떠진 느낌이다. 하지만 아직 부족하니 좀더 문제를 풀어야 겠다. 밑은 내가 작성한 코드이다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static int[] dY = new int[] {0,-1,0,1};
    private static int[] dX = new int[] {-1,0,1,0};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        boolean[][] visited = new boolean[n][m];
        //맵을 넣을 배열
        int[][] map = new int[n][m];
        //그룹id를 저장할 배열
        int[][] groupIdmap = new int[n][m];
        //그룹id가 각 갈수있는 최대 길이를 담을 배열
        int[] lengthList = new int[n*m+1];

        for(int i=0;i<n;i++) {
            String mapinfo = br.readLine();
            for(int j=0;j<m;j++) {
                map[i][j] = mapinfo.charAt(j)-'0';
            }
        }


        //전체 배열을 이중for문으로 돌면서 0을 만날때 BFS 돌림
        int groupId = 0;
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(map[i][j] == 1) continue;
                if(groupIdmap[i][j]==0) {
                    int length = bfs(i,j,n,m,map,groupIdmap,++groupId, visited);
                    lengthList[groupId] = length;
                }
            }
        }
        //printMap(n,m,map,groupIdmap,lengthList);

        //위 작업 끝나면 groupIdmap에는 그룹핑된 인덱스 정보가 있고
        //lengthList에는 각 그룹이 가지고있는 최대 길이 정보가 들어가있게 됨
        //전체 칸 돌면서 1일때 이동할수 있는 칸 출력 0일때는 0출력
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(map[i][j] == 0) {
                    bw.append("0");
                    continue;
                }else if(map[i][j]==1) {
                    //주변 노드들 탐색해서 주변 노드의 groupid를 해쉬에 삽입
                    HashSet<Integer> hash = new HashSet<Integer>();
                    for(int k=0;k<4;k++) {
                        int nx = i+dX[k];
                        int ny = j+dY[k];

                        if(nx>=0 && ny>=0 && nx<n && ny<m && map[nx][ny]==0 && !hash.contains(groupIdmap[nx][ny])) {
                            hash.add(groupIdmap[nx][ny]);
                        }

                    }
                    int sum=1;
                    for(int groupid : hash) {
                        sum += lengthList[groupid];
                    }
                    bw.append(Integer.toString(sum%10));

                }
            }
            bw.append("\n");

        }

        bw.flush();
    }
    public static void printMap(int n, int m, int[][] map, int[][] groupIdmap,int [] lengthList) {
        System.out.println("map:");
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                System.out.print(map[i][j]);
            }
            System.out.println();
        }
        System.out.println("groupidmap");
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                System.out.print(groupIdmap[i][j]);
            }
            System.out.println();
        }
        System.out.println("lengthList");
        for(int i=0;i<6;i++) {
            System.out.print(lengthList[i]+" , ");
        }
        System.out.println();
    }

    //param:1) 현재 노드의 x행값, 2)현재노드의 열값 3)맵의 전체 행값 4)맵의 전체 열값 5)맵 배열 6)그룹id담을 배열 7)넣은 그룹 id
    //현재 0이 갈수있는 길이의 최대값을 리턴
    private static int bfs(int x, int y, int N, int M, int[][] map, int[][] groupIdmap, int groupId, boolean[][] visited) {
        Queue<Pair> que = new LinkedList<Pair>();

        que.add(new Pair(x,y));
        visited[x][y] = true;
        groupIdmap[x][y] = groupId;
        int length=0;

        while(!que.isEmpty()) {
            Pair node = que.poll();
            length++;

            //주변에 0 있는지 없는지 체크
            for(int i=0;i<4;i++) {
                int nx = node.x+dX[i];
                int ny = node.y+dY[i];
                //맵의 안에 잇고, 0이면서 방문하지 않았으면
                if(nx>=0 && ny>=0 && nx<N && ny<M && map[nx][ny] == 0 && !visited[nx][ny]) {
                    que.add(new Pair(nx,ny));
                    visited[nx][ny] = true;
                    groupIdmap[nx][ny] = groupId;
                }
            }
        }
        return length;
    }
    public static class Pair{
        int x,y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}