La foret rouge
Published on

백준 2931: 가스관

Authors
  • avatar
    Name
    신주용

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

문제 이해

boj 2931
boj 2931
  • 공백('.')을 파이프 블록으로 바꿔 M에서 Z로 가는 파이프 경로를 이어야 합니다.
  • 항상 답이 존재하고, 가스의 흐름이 유일한 경우만 입력으로 주어지므로 공백 주변의 파이프롤 확인하여 이어주기만 하면 됩니다.

접근 방법

  • 문제에서 M에서 Z로 가는 경로를 물어서 처음에는 DFS, BFS 같은 탐색으로 풀어야 할 것 같은 느낌이 강하게 들었으나, 생각을 하다보니 그래프 탐색으로 풀려면 복잡할 것 같습니다.
  • 유럽의 크기가 25×2525 \times 25이므로 과감하게 이차원 배열 탐색을 시도했습니다.
  • 모든 칸을 방문하면서 공백('.') 문자를 발견하면 주변 십자가 모양으로 네 칸을 확인합니다.
  • 만약 주변 네 칸이 모두 블록 또는 시작/도착 지점이라면
    • 주변 네 칸 중 두 칸에 시작/도착 지점이 있는 경우 이를 직접 연결하면 불필요한 블록이 무조건 생겨버리므로 이를 회피하는 조건을 추가할 필요가 있습니다. (질문 게시판 글12 참고)
    • 주변 네 칸이 모두 파이프인 경우는 '+' 모양 칸으로 이어줍니다.
  • 그 외 경우는 주변 네 칸 중 파이프가 있는 두 칸을 보고 이어줍니다.

코드

public class Main {

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

    String[] RC = br.readLine().split(" ");
    int R = Integer.parseInt(RC[0]);
    int C = Integer.parseInt(RC[1]);

    char[][] map = new char[R][C];
    for (int r = 0; r < R; r++) {
      map[r] = br.readLine().toCharArray();
    }

    loop: for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (map[i][j] != '.') continue;

        boolean u = i - 1 < 0 ? false : "|+14MZ".contains(map[i - 1][j] + "");
        boolean d = i + 1 >= R ? false : "|+23MZ".contains(map[i + 1][j] + "");
        boolean l = j - 1 < 0 ? false : "-+12MZ".contains(map[i][j - 1] + "");
        boolean r = j + 1 >= C ? false : "-+34MZ".contains(map[i][j + 1] + "");

        char block = 0;
        if (u && d && l && r){
          if ("MZ".contains(map[i-1][j] + "")  && "MZ".contains(map[i+1][j] + "")) block = '-';
          else if ("MZ".contains(map[i][j - 1] + "")  && "MZ".contains(map[i][j+1] + "")) block = '|';
          else if ("MZ".contains(map[i][j - 1] + "")  && "MZ".contains(map[i - 1][j] + "")) block = '1';
          else if ("MZ".contains(map[i][j - 1] + "")  && "MZ".contains(map[i + 1][j] + "")) block = '2';
          else if ("MZ".contains(map[i][j + 1] + "")  && "MZ".contains(map[i + 1][j] + "")) block = '3';
          else if ("MZ".contains(map[i][j + 1] + "")  && "MZ".contains(map[i - 1][j] + "")) block = '4';
          else block = '+';
        }
        else if (u && l) block = '3';
        else if (u && d) block = '|';
        else if (u && r) block = '2';
        else if (l && d) block = '4';
        else if (l && r) block = '-';
        else if (d && r) block = '1';

        if (block == 0) continue;
        sb.append(String.format("%d %d %c\n", i + 1, j + 1, block));
        break loop;
      }
    }
    System.out.println(sb);
  }
}

결과

첫 시도에는 질문 글에 있는 Counter example을 놓쳐 실패했습니다. 제출하기 전 조금 더 다양한 케이스를 고민하는 습관을 들여야겠다고 생각했습니다. 이 문제를 그래프 탐색으로 구현하더라도 코드가 크게 바뀌지는 않을 것 같습니다.

  • 2차원 배열 탐색 대신 M의 좌표부터 바로 시작할테고,
  • 문제에서 시작점과 종료 지점은 하나의 블록만 인접해 있다고 했으니 따라가면 될 것입니다.
  • 파이프 블록을 따라가다 블록을 만나면 위 코드와 동일하게 사방의 파이프 블록을 확인할 것이고
  • 문제에서 없어진 블록을 추가하면 모든 블록에 가스가 흐르게 된다고 했으므로 파이프 블록 연결 후 바로 탐색 종료하도록 구현하면 될 것 같습니다.

Prerequisites: 이 글에서 언급되었으나 깊게 설명하지 않은 내용입니다.

Footnotes

  1. https://www.acmicpc.net/board/view/33842

  2. https://www.acmicpc.net/board/view/55108