[BOJ] 16946번: 벽 부수고 이동하기 4

문제 내용

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

16946번: 벽 부수고 이동하기 4

 

풀이 시간

45분

풀이 과정

문제에 써있는 방식 그대로 각 벽마다 BFS를 실행하였다. -> 시간초과

역으로 생각해서 빈곳들의 크기를 구하고 빈곳의 값을 개수로 넣어줬다.

이후 각 벽마다 사방의 빈곳의 개수의 합+1을 넣었다.-> 오답

=> 벽 주위의 빈곳들이 서로 연결되어 있는 경우를 고려하지 못했다.

Map을 사용해서 각 빈 그룹별 개수를 넣었다. 이후 빈곳의 값을 개수가 아닌 해당 키값을 넣었다.

 

이후 벽의 사방을 조회할때 사방의 그룹들의 키값을 유니크하게 가져오고 이를 Map에 조회해서 합을 구했다.

=> 정답!

 

정답 코드

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


public class Main {
    static int N,M;
    static int[][]arr;
    static int[][]mv={{1,0},{-1,0},{0,1},{0,-1}};
    static Map<Integer,Integer> group=new HashMap<>();
    static int keyIndex=-1;

    public static void main(String[] args) throws Exception {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        StringBuilder sb=new StringBuilder();
        N=Integer.parseInt(st.nextToken());
        M=Integer.parseInt(st.nextToken());

        arr=new int [N][M];

        for(int i=0;i<N;i++){
            char[] input=br.readLine().toCharArray();

            for(int j=0;j<M;j++){
                arr[i][j]=input[j]-'0';
            }
        }

        //fill
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(arr[i][j]==0){
                    fill(i,j);
                }
            }
        }



        //check
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(arr[i][j]==1){
                    int sum=0;
                    Set<Integer> s=new HashSet<>();
                    for(int[]next:mv){
                        int nx=i+next[0];
                        int ny=j+next[1];

                        if(nx<0||nx==N||ny<0||ny==M) continue;

                        if(arr[nx][ny]>0) continue;

                        s.add(arr[nx][ny]);
                    }

                    for(int x: s){
                        sum+=group.get(x);
                        sum%=10;
                    }

                    sb.append((sum+1)%10);
                }
                else{
                    sb.append(0);
                }
            }
            sb.append('\n');
        }

        System.out.println(sb);
    }

    static void fill(int x,int y){
        Set<Point> visited=new HashSet<>();
        Deque<Point> dq=new ArrayDeque<>();
        dq.add(new Point(x,y));
        visited.add(new Point(x,y));


        while(!dq.isEmpty()){
            Point cur=dq.poll();

            for(int[]next:mv){
                int nx=cur.x+next[0];
                int ny=cur.y+next[1];

                if(nx<0||nx==N||ny<0||ny==M) continue;

                Point nPoint=new Point(nx,ny);

                if(visited.contains(nPoint) || arr[nx][ny]!=0) continue;
                dq.add(nPoint);
                visited.add(nPoint);
            }
        }

        for(Point p:visited){
            arr[p.x][p.y]=keyIndex;
        }

        group.put(keyIndex--,visited.size());


    }

    static class Point{
        int x,y;

        public Point(int x,int y){
            this.x=x;
            this.y=y;
        }

        @Override
        public boolean equals(Object obj) {
            Point o=(Point) obj;

            return x==o.x&&y==o.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }


}