BOJ) 체스판 위의 공

체스판 위의 공

16957번: 체스판 위의 공

풀이

 

체스판의 크기가 500x500이지만, 공들이 옮겨가면서 0인 부분이 많이 생길거라고 생각하고 DFS로 진행했다.

하지만, 6%에서 시간초과가 떴고 DFS로는 풀 수 없는 문제라고 생각이 들었다.

그래서 인접한 칸들 중 가장 작은 숫자로 이동한다는 조건을 보고, find-union을 응용하면 풀 수 있을거라고 생각했다.

 

일단, union부분은 필요가 없다고 생각을 했다.

생각하기도 복잡해지고, 타고 타고 이동해야하는 특성상 parents만 조정하기로 했다.

 

우선, 맵을 돌면서 각 지점마다 현재의 칸과 인접한 칸 중 가장 작은 칸으로 parents를 설정해주었다.

2차원 배열은 좌표를 저장하기가 애매해져서, 모든 칸에 인덱스를 부여해서 관리했다.

또한, 설정을 할 때, dfs를 통해서 저장해줬다.

 

저장이 끝난 이후에는, 저장된 parents를 타면서 find 된 가장 parent 부분에 값을 증가시키면서 이동된 구슬의 값을 저장했다.

 

위의 과정 마저 끝나면, 모든 좌표를 돌면서 StringBuffer에 값을 담아 출력을 준비했다.

 

3번의 과정을 돌면서, 답을 구할 수 있었다.

 

 

 

 

시간초과 코드 (DFS)

 

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

public class Main {
    final static int[] dx = {0,1,1,1,0,-1,-1,-1}, dy = {-1,-1,0,1,1,1,0,-1};
    final static int MAX_VALUE = 300001;
    static int maxY, maxX;
    static int[][] balls;

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

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

        int[][] map = new int[maxY][maxX];
        balls = new int[maxY][maxX];

        for(int i=0; i<maxY; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<maxX; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                balls[i][j] = 1;
            }
        }

        solution(map);
        br.close();
    }

    private static void solution(int[][] map) {
        StringBuffer sb = new StringBuffer();
        final String space = " ", newLine = "\n";
        for(int y=0; y<maxY; y++) {
            for(int x=0; x<maxX; x++) {
                if(balls[y][x] !=0) {
                    dfs(x,y,map);
                }
            }
        }

        for(int y=0; y<maxY; y++) {
            for(int x=0; x<maxX; x++) {
                sb.append(balls[y][x]).append(space);
            }
            if(y <maxY-1) { sb.append(newLine); }
        }
        System.out.println(sb.toString());
    }

    private static void dfs(int x, int y, int[][] map) {
        int min = MAX_VALUE;
        int minX=0, minY=0;

        for(int i=0; i<8; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isInArea(nx,ny)) {
                if(min > map[ny][nx]) {
                    min = map[ny][nx];
                    minX = nx;
                    minY = ny;
                }
            }
        }
        if(min < map[y][x]) {
            balls[minY][minX] += balls[y][x];
            balls[y][x] =0;
            dfs(minX, minY, map);
        }
    }

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

 

통과 코드 (find-union)

 

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

public class Main {
    final static int[] dx = {0,1,1,1,0,-1,-1,-1}, dy = {-1,-1,0,1,1,1,0,-1};
    final static int MAX_VALUE = 300001;
    static int maxY, maxX;
    static int[] parents;

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

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

        int[][] map = new int[maxY][maxX];
        parents = new int[maxY*maxX];

        for(int i=0; i<maxY; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<maxX; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                parents[i*maxX+j] = i*maxX+j;
            }
        }

        solution(map);
        br.close();
    }

    private static void solution(int[][] map) {
        StringBuffer sb = new StringBuffer();
        final String space = " ", newLine = "\n";
        for(int y=0; y<maxY; y++) {
            for(int x=0; x<maxX; x++) {
                if(parents[y*maxX+x] ==y*maxX+x) {
                    dfs(x,y,map);
                }
            }
        }

        int mul = maxX*maxY;
        int[] answer = new int[mul];

        for(int i=0; i<mul; i++) {
            answer[find(i)]++;
        }

        for(int y=0; y<maxY; y++) {
            for(int x=0; x<maxX; x++) {
                sb.append(answer[y*maxX+x]).append(space);
            }
            sb.append(newLine);
        }
        System.out.println(sb.toString());
    }

    private static int find(int val) {
        if(val == parents[val]) { return val; }
        return parents[val] = find(parents[val]);
    }

    private static void dfs(int x, int y, int[][] map) {
        int min = MAX_VALUE;
        int minX=0, minY=0;

        for(int i=0; i<8; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isInArea(nx,ny)) {
                if(min > map[ny][nx]) {
                    min = map[ny][nx];
                    minX = nx;
                    minY = ny;
                }
            }
        }
        if(min < map[y][x]) {
            if(parents[y*maxX+x] == maxX*y+x) {
                parents[y*maxX+x] = minY * maxX + minX;
                dfs(minX, minY, map);
            }
        }
    }

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