BOJ) 연구소

연구소

14502번: 연구소

풀이

 

배열 복사 문제로 고생을 조금 했다. 바이러스가 퍼지는 부분을 갱신할 때, 기존 MAP에 덮어 씌우면 답과 거리가 멀어지기 때문이다.

왜냐하면, char[][] map은 dfs에 계속 이용이 되기 때문에.. 다른 값들에 영향을 미친다.

배열 복사 이후에 바이러스가 퍼지고, 안전 구역을 탐색하니까 답을 맞출 수 있었다.

 

일단 3번 답을 구했는데, 첫번째로 구했던 답은 LinkedList를 이용하는 것이었다.

바이러스를 퍼뜨릴 때, LinkedList를 이용해서 BFS로 풀었었는데, 메모리 공간이 굉장히 낭비됐다.

(DFS 안에서 BFS를 돌린다는 것 자체가 비효율적이기는 하다.. 문제 분류가 BFS라 BFS를 적용하려고 했던 것 같다..)

 

그래서 두번째 코드 처럼, 그냥 DFS로 바이러스를 뿌려줬다.

시간과 메모리에서 훨씬 효율적으로 움직이는 것을 확인할 수 있다.

 

그 다음에는, for문을 돌리는 법이나 자잘한 부분을 고쳐줬는데, 효율성이 오히려 떨어져서 따로 코드를 남기지는 않겠다..

 

코드 2도 매우 효율적이라고는 말할 수 없는 코드지만, 문제 풀이 방법에 대해 합격점을 받을만한 코드라고 생각한다.

 

아, 그리고 아래에 x와 y좌표를 탐색할 때 1중 for문을 통해서 좌표를 설정해주었는데, 질문하기 게시판에서 본 방법이다.

정말 참신한 방법이다.

for문을 x와 y좌표 최대값 까지 돌면서, y좌표는 x 최대값으로 나눈 값의 몫, x좌표는 나머지 값으로 좌표를 설정하면 1중으로도 돌릴 수 있었다.

훨씬 깔끔하고 보기 좋았다.. 기억에 남겨두려고 이번 코드에 적용해봤다.

 

코드 1

 

private static void getSafeArea(int n, int m, char[][] map, int cnt, int mul) {
        if(cnt ==0) {
            LinkedList<int[]> virusList = new LinkedList<>();
            boolean[][] visit = new boolean[n][m];
            char[][] newMap = copyMap(n,m,map);
            for(int y=0; y<n; y++) {
                for(int x=0; x<m; x++) {
                    if(!visit[y][x] && newMap[y][x] == VIRUS) {
                        virusList.offer(new int[]{x,y});
                        visit[y][x] = true;
                        while(!virusList.isEmpty()) {
                            int[] pos = virusList.poll();

                            for(int i=0; i<4; i++) {
                                int nx = pos[0] + dx[i];
                                int ny = pos[1] + dy[i];
                                if(inInArea(nx,ny,m,n)) {
                                    if(newMap[ny][nx] == BLANK) {
                                        newMap[ny][nx] = VIRUS;
                                        visit[ny][nx] = true;
                                        virusList.offer(new int[]{nx,ny});
                                    }
                                }
                            }
                        }
                    }
                }
            }

            int safeArea =0;
            for(int y=0; y<n; y++) {
                for(int x=0; x<m; x++) {
                    if(newMap[y][x] == BLANK) {
                        safeArea++;
                    }
                }
            }
            answer = Math.max(answer,safeArea);
            return;
        }

        for(int step = mul; step <n*m; step++) {
            int y = step/m;
            int x = step%m;
            if(map[y][x] == BLANK) {
                map[y][x] = WALL;
                getSafeArea(n,m,map,cnt-1, mul+1);
                map[y][x] = BLANK;
            }
        }
    }

    private static char[][] copyMap(int n, int m, char[][] map) {
        char[][] result = new char[n][m];
        for(int y=0; y<n; y++) {
            for(int x=0; x<m; x++) {
                result[y][x] = map[y][x];
            }
        }
        return result;
    }

    private static boolean inInArea(int x, int y, int m, int n) {
        return x>=0 && x<m && y>=0 && y<n ? true : false;
    }

 

코드 2

 

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

public class LAB_14502 {
    final static char BLANK ='0', WALL = '1', VIRUS ='2';
    final static int[] dx = {1,0,-1,0}, dy ={0,1,0,-1};
    static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        char[][] map = new char[n][m];

        for(int i=0; i<n; i++) {
            map[i] = br.readLine().replaceAll(" ","").toCharArray();
        }
        solution(n,m,map);

        br.close();
    }

    private static void solution(int n, int m, char[][] map) {
        answer =0;
        getSafeArea(n,m,map,3,0);
        System.out.println(answer);
    }

    private static void getSafeArea(int n, int m, char[][] map, int cnt, int mul) {
        if(cnt ==0) {
            char[][] newMap = copyMap(n,m,map);
            for(int y=0; y<n; y++) {
                for(int x=0; x<m; x++) {
                    if(newMap[y][x] == VIRUS) {
                        newMap = spread(x,y,newMap);
                    }
                }
            }

            int safeArea =0;
            for(int y=0; y<n; y++) {
                for(int x=0; x<m; x++) {
                    if(newMap[y][x] == BLANK) {
                        safeArea++;
                    }
                }
            }
            answer = Math.max(answer,safeArea);
            return;
        }

        for(int step = mul; step <n*m; step++) {
            int y = step/m;
            int x = step%m;
            if(map[y][x] == BLANK) {
                map[y][x] = WALL;
                getSafeArea(n,m,map,cnt-1, mul+1);
                map[y][x] = BLANK;
            }
        }
    }

    private static char[][] spread(int x, int y, char[][] newMap) {
        for(int i=0; i<4; i++) {
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(isInArea(nx,ny,newMap[0].length, newMap.length)) {
                if(newMap[ny][nx] == BLANK) {
                    newMap[ny][nx] = VIRUS;
                    spread(nx,ny,newMap);
                }
            }
        }
        return newMap;
    }

    private static char[][] copyMap(int n, int m, char[][] map) {
        char[][] result = new char[n][m];
        for(int y=0; y<n; y++) {
            for(int x=0; x<m; x++) {
                result[y][x] = map[y][x];
            }
        }
        return result;
    }

    private static boolean isInArea(int x, int y, int m, int n) {
        return x>=0 && x<m && y>=0 && y<n ? true : false;
    }
}