BOJ) 벽 부수고 이동하기 4

벽 부수고 이동하기 4

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

풀이

 

처음에는 모든 벽에 대해서 벽을 허물고 값을 구하고자 했다.

하지만, 주어진 n과 m의 최대값이 1000이나 되기 때문에 시간초과가 뜰 것 같았다.

그래서 생각한 것은 0에 대해서 grouping을 해주는 것이다.

빈칸이 이어진 곳들에 대해서 그룹 index를 남기고, 몇 개의 빈칸이 존재하는지 세주어서 저장하는 것이다.

 

이후에, Map을 돌면서 벽을 허물었을 경우, 상하좌우에 (인접한 곳에) 빈칸 그룹이 가지고 있는 총 count 수 +1개가 벽을 허문 경우에 이동할 수 있는 경우의 수라고 생각했다. 그래서, 벽의 상하좌우에 있는 빈칸 그룹을 LinkedList에 중복 확인을 하면서 저장했다.

List에 있는 index를 빼면서 벽에 이동 가능한 횟수를 저장했다.

 

문제를 맞기는 했지만, 이것도 효율적이지는 못했다.

 

 

다시 풀어보려고 했지만, 아까 문제를 조금 오래풀어서 힘들었다.

그래서 나중에 다시 풀기로 다짐하고 넘겼다..

풀어도 풀어도 효율적인 코드를 시간안에 바로 짜기는 정말 힘든 것 같다..

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    private static int[] dx = {1,0,-1,0}, dy = {0,1,0,-1};
    private static char WALL = '1', BLANK = '0';

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

        int maxY = Integer.parseInt(st.nextToken());
        int maxX = Integer.parseInt(st.nextToken());

        char[][] map = new char[maxY][maxX];
        for(int i=0; i<maxY; i++) {
            map[i] = br.readLine().toCharArray();
        }

        solution(maxX, maxY, map);

        br.close();
    }

    private static void solution(int maxX, int maxY, char[][] map) {
        int[][] move = new int[maxY][maxX];

        LinkedList<Dot> moveList = new LinkedList<>();
        HashMap<Integer,Integer> groupCnt = new HashMap<>();
        int group =0;

        for(int y=0; y<maxY; y++) {
            for(int x=0; x<maxX; x++) {
                if(map[y][x] == BLANK && move[y][x] ==0) {
                    int cnt=0;
                    move[y][x] = ++group;
                    moveList.offer(new Dot(x,y));

                    while(!moveList.isEmpty()) {
                        Dot pos = moveList.poll();
                        cnt++;

                        for(int i=0; i<4; i++) {
                            int nx = pos.x+dx[i];
                            int ny = pos.y+dy[i];

                            if(isInArea(nx,ny,maxX,maxY)) {
                                if(move[ny][nx] ==0 && map[ny][nx] == BLANK) {
                                    move[ny][nx] = group;
                                    moveList.offer(new Dot(nx, ny));
                                }
                            }
                        }
                    }
                    groupCnt.put(group, cnt%10);
                }
            }
        }
        int mul = maxX*maxY;
        LinkedList<Integer> blankList = new LinkedList<>();
        for(int i=0; i<mul; i++) {
            int y = i/maxX;
            int x = i%maxX;
            if(map[y][x]==WALL) {
                for(int j=0; j<4; j++) {
                    int nx = x +dx[j];
                    int ny = y +dy[j];
                    if(isInArea(nx,ny,maxX,maxY)) {
                        if(map[ny][nx] == BLANK && !blankList.contains(move[ny][nx])) {
                            blankList.offer(move[ny][nx]);
                        }
                    }
                }
                while(!blankList.isEmpty()) {
                    move[y][x] += groupCnt.get(blankList.poll());
                }
                move[y][x] = (move[y][x]+1)%10;
            }
        }

        for(int y=0; y<maxY; y++) {
            for(int x=0; x<maxX; x++) {
                if(map[y][x] == WALL) {
                    System.out.print(move[y][x]);
                } else {
                    System.out.print(BLANK);
                }
            }
            System.out.println();
        }
    }

    private static boolean isInArea(int x, int y, int maxX, int maxY) {
        return x >=0 && x<maxX && y>=0 && y<maxY;
    }
}

class Dot {
    int x;
    int y;

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