백준 21736번: 헌내기는 친구가 필요해

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

문제를 보고 그래프이론으로 풀 수 있겠다 싶었다.

우선 2차원 배열을 만들어서 입력받는데 2차원의 크기를 [n + 2][m + 2]로 만들어주었다.

상하좌우에 빈칸을 하나 씩 만들어서 탐색하다가 인덱스를 벗어나지 않게 하기 위함이다.

또한 I의 위치부터 탐색하기 위해서 I를 입력받은 위치를 기억했다.

 

그 다음에는 I부터 시작해서 상하좌우에 P가 있는지 계속 탐색하게 코드를 만들었다.

만약 탐색하는 위치가 'X'거나 char의 기본값인 '\u0000'이라면 멈추고,

만약 'P'라면 1을 더한 후 탐색을 더 하도록 했다.

 

그렇게 탐색을 끝냈을 때 만약 그 값이 0이라면 TT를 출력하고,

아니라면 탐색해서 나온 값을 출력하게 했다.

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

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

    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int x = 0; int y = 0;
    campus = new char[N + 2][M + 2];

    for (int n = 1; n <= N; n++) {
      String line = br.readLine();
      for (int m = 1; m <= M; m++) {
        campus[n][m] = line.charAt(m - 1);
        if (line.charAt(m - 1) == 'I') {
          x = n; y = m;
        }
        
      }
    }

    int res = DFS(x, y);
    if (res == 0) sb.append("TT");
    else sb.append(res);

    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    bw.write(sb + "");
    bw.flush();
    bw.close();
  }

  static int DFS(int x, int y) {
    if (campus[x][y] == '\u0000' || campus[x][y] == 'X') return 0;

    if (campus[x][y] == 'P') {
      campus[x][y] = 'X';
      return DFS(x + 1, y) + DFS(x - 1, y) + DFS(x, y + 1) + DFS(x, y - 1) + 1;
    }
    else  {
      campus[x][y] = 'X';
      return DFS(x + 1, y) + DFS(x - 1, y) + DFS(x, y + 1) + DFS(x, y - 1);
    }
  }
}