[BOJ] 25552번 : 잔디 예측하기 Java 풀이

처음에 문제를 잘못이해해서 맞왜틀을 했다.

구하고 싶은 값을 아주 간단하게 정의하면 초기의 잔디 상태가 주어졌을때, 결과로 주어진 잔디 상태를 만들 수 있는가?를 묻고 있다.
처음 주어지는 잔디를 graph, 최후의 잔디를 result라고 일단  정의를 했다. 만약 graph에서 O인데 result에서 X인 상태가 주어진다면 절대 만들 수 없다. 나는 이 부분을 놓쳤고 O를 전부 채우기만 하면 된다고 문제를 접근해 자꾸 틀렸다.

이 부분을 고려했다면 이제 result 잔디를 만들 수 있는지 확인해야 한다. 나는 BFS와 DFS를 적절히 섞어 문제를 해결했다.

먼저 초기 잔디를 기준으로 BFS를 돌릴것이다. 근데, 최대 D만큼 이동해 잔디를 채울 수 있다. 이때 지나간길을 전부 잔디로 채우지 않아도 된다. 초기 위치를 전부 큐에 넣고 BFS를 돌리자. 이때 꺼낸 노드는 DFS 탐색을 통해 result 에서 O인 구역을 전부 칠하면 된다.

D가 최대 8이라서 백트래킹을 생각해볼 수 있는데, 그러면 시간복잡도가 터져버린다. 만약 백트래킹을 돌려 모든 칸을 확인하고자 한다면, 최대 O(4^8 * N * M)이 소요된다. 따라서 시간복잡도를 줄여야 하는데, 나는 3차원 배열로 방문을 표시해 시간을 줄였다. 그러면 현재까지 이동한 거리를 k라고 하고, 좌표를 (i, j)라고 할때 visited[k][i][j]로 방문을 표시할 수 있다.

이제 이 방문값을 기준으로 BFS를 돌리면서 잔디만 찾아 영역을 확장하면 O(DNM)에 모든 방문을 확인할 수 있다. 모든 방문을 확인했다면, result 배열에서 O로 표시된 좌표를 방문한적 있는지 없는지 확인하고, 모든 O에 대하여 방문할 수 있다면 YES를 아니라면 NO를 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Queue;

public class Main {

  private static final Queue<Node> q = new LinkedList<>();
  private static final List<String>[] graph = new ArrayList[1010];
  private static final List<String>[] result = new ArrayList[1010];
  private static final boolean[][][] visited = new boolean[10][1010][1010];
  private static final int[] dx = {1, -1, 0, 0};
  private static final int[] dy = {0, 0, -1, 1};

  private static Boolean flag = true;
  private static int N;
  private static int M;
  private static int K;

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

    N = Integer.parseInt(str[0]);
    M = Integer.parseInt(str[1]);
    for (int i = 0; i < N; i++) {
      String s = br.readLine();
      graph[i] = new ArrayList<>();
      graph[i].add(s);
    }

    K = Integer.parseInt(br.readLine());
    for (int i = 0; i < N; i++) {
      String s = br.readLine();
      result[i] = new ArrayList<>();
      result[i].add(s);
    }

    clearVisited();
    bfs();
    calFlag();
    if (!flag) {
      System.out.println("NO");
    } else {
      System.out.println("YES");
    }
  }


  private static void calFlag() {

    for (int i=0; i<N; i++) {
      for (int j=0; j<M; j++) {
        if (graph[i].get(0).charAt(j) == 'O' && result[i].get(0).charAt(j) == 'X') {
          flag = false;
          return;
        }
      }
    }

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        boolean isValid = false;
        for (int k=0; k<=K; k++) {
          if (visited[k][i][j]) {
            isValid = true;
          }
        }
        if (!isValid && Objects.equals(result[i].get(0).charAt(j), 'O')) {
          flag = false;
          return;
        }
      }
    }
  }

  private static void clearVisited() {
    for (int k=0; k<=K; k++) {
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
          visited[k][i][j] = false;
        }
      }
    }
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < M; j++) {
        if (Objects.equals(graph[i].get(0).charAt(j), 'O')) {
          q.add(new Node(i, j, 0));
          visited[0][i][j] = true;
        }
      }
    }
  }

  private static void bfs() {
    while (!q.isEmpty()) {
      Node node = q.poll();
      dfs(node);
    }
  }

  private static void dfs(Node node) {
    if (node.dist == K) {
      return;
    }
    for (int i = 0; i < 4; i++) {
      int nx = node.x + dx[i];
      int ny = node.y + dy[i];
      if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[node.dist+1][nx][ny]) {
        continue;
      }
      visited[node.dist+1][nx][ny] = true;
      if (Objects.equals(result[nx].get(0).charAt(ny), 'O')) {
        q.add(new Node(nx, ny, 0));
      } else {
        dfs(new Node(nx, ny, node.dist + 1));
      }
    }
  }

  static class Node {
    private final int x;
    private final int y;
    private final int dist;

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