[백준] 14502.연구소 - Java

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

 

<풀이>

백트래킹 부분에서 삽질을 많이 했다. 알고리즘 푸는 것처럼 코드를 작성하는게 아닌, 실제 파라미터를 사용해서 값을 주고받고, 백트래킹 부분에서 조건을 만족하면 BFS를 돌리는 것이 아니라, 일부러 모든 경우의 수의 연구소 map을 ArrayList에 담으려고해봤는데, 도저히 전역변수를 사용하지 않고 문제를 해결하는 방법이 떠오르지 않아 아래와 같이 코드를 작성했다.

 

추후에는 setWall에서 ArrayList<char[][]> 형식의 연구소 맵의 모든 경우의 수를 반환하는 함수를 만들어 각자 따로 bfs에 넣고 돌려보고자한다.

import java.util.*;
import java.io.*;

public class P14502 {

    static class Node {
        int x;
        int y;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static BufferedReader br;
    private static BufferedWriter bw;
    private static StringTokenizer st;
    private static int n;
    private static int m;
    private static char[][] map;
    private static int[] dx = {0, 0, -1, 1};
    private static int[] dy = {-1, 1, 0, 0};
    private static int answer;
    private static ArrayList<Node> virus;

    private static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new char[n][m];
        virus = new ArrayList<>();
        answer = 0;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = st.nextToken().charAt(0);
                if (map[i][j] == '2') {
                    virus.add(new Node(j, i));
                }
            }
        }
    }

    private static void solution() {
        setWall(0);
    }

    private static void setWall(int wallCount) {
        if (wallCount == 3) {
            bfs();
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == '0') {
                    map[i][j] = '1';
                    setWall(wallCount + 1);
                    map[i][j] = '0';
                }
            }
        }
    }

    private static void bfs() {
        Deque<Node> q = new LinkedList<>();
        int count = 0;
        boolean[][] visited = new boolean[n][m];
        for (int i = 0; i < virus.size(); i++) {
            Node v = virus.get(i);
            q.add(v);
            visited[v.y][v.x] = true;
        }

        char[][] copyMap = deepCopyMap(map);

        while (!q.isEmpty()) {
            Node curNode = q.remove();
            int curX = curNode.x;
            int curY = curNode.y;

            for (int i = 0; i < 4; i++) {
                int nextX = curX + dx[i];
                int nextY = curY + dy[i];

                if (isInRange(nextX, nextY) && !visited[nextY][nextX]) {
                    if (copyMap[nextY][nextX] == '0') {
                        copyMap[nextY][nextX] = '2';
                        q.add(new Node(nextX, nextY));
                        visited[nextY][nextX] = true;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyMap[i][j] == '0') {
                    count++;
                }
            }
        }

        if (count > answer) {
            answer = count;
        }

    }

    private static boolean isInRange(int x, int y) {
        if (0 <= y && y < n && 0 <= x && x < m) {
            return true;
        }
        return false;
    }

    private static char[][] deepCopyMap(char[][] origin) {
        char[][] newMap = new char[n][m];
        for (int i = 0; i < origin.length; i++) {
            // System.arraycopy(원본 배열, 원본 배열의 복사를 시작할 인덱스, 새로운 배열, 새로운 배열에서 복사를 시작할 인덱스, 복사할 요소 개수);
            System.arraycopy(origin[i], 0, newMap[i], 0, origin[i].length);
        }
        return newMap;
    }

    public static void main(String[] args) throws IOException {
        init();

        solution();

        bw.write(String.valueOf(answer));

        bw.flush();
        bw.close();
        br.close();
    }
}