유기농 배추(1012)

유기농 배추(1012)

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

public class Main{
    
  static int[][] arr;
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int t = Integer.parseInt(br.readLine());
    
    while(t-- > 0){
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), k = Integer.parseInt(st.nextToken());
      
      arr = new int[n+2][m+2]; // 밭의 주변을 모두 0으로 감싸기 위해서
      
      int cnt = 0;
      
      for(int i = 0; i < k; i++){
        st = new StringTokenizer(br.readLine());
        
        int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
        
        arr[a+1][b+1]++; // 밭의 주변을 0으로 감쌓기 때문에 인덱스가 증가하였으므로 입력값에 +1을 해준다
      }
      
      for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
          if(arr[i][j] == 1){
            boolean res = change(arr, i, j);
            if(res) cnt++;
          }
        }
      }
      
      sb.append(cnt).append("\n");
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static boolean change(int[][] arr, int i, int j){
    boolean flag = false;
    
    arr[i][j] = 2; // 체크된 배추의 값을 1에서 2로 바꿔준다.
    
    if(arr[i][j-1] == 1) flag = change(arr, i, j-1); // 왼쪽에 체크가 안된 배추가 있으면 다시 함수 호출
    else flag = true;
    
    if(arr[i][j+1] == 1) flag = change(arr, i, j+1); // 우측
    else flag = true;
    
    if(arr[i-1][j] == 1) flag = change(arr, i-1, j); // 위
    else flag = true;
    
    if(arr[i+1][j] == 1) flag = change(arr, i+1, j); // 아래
    else flag = true;
    
    return flag; // 연결된 모든 배추들의 값이 1이 없으면 true 반환. 즉, 체크가 되서 2가 됬거나 아니면 공터이거나
  }
}

풀이과정

1. 처음에는 for문을 사용하여 인덱스가 증가하기 때문에 좌측에서 우측으로, 위에서 아래로 체크해 나가면 된다고 생각하였다.
2. 하지만 여러 경우의 수를 생각해 보니 그렇게 하면 같은 가로줄에 있지만 중간에 공터가 있는 상황에서 아래쪽으로 배추들이 이어지는 형태가 되면 지렁이가 1마리가 아니라 2마리가 체크된다는 것을 알게되었다.
3. 그래서 기준점에서 좌우 위아래를 모두 계속해여 판단하며 나아가야 하는데 어떠한 지점이 사방에 계속하여 배추가 있으면 어느 지점으로 넘어갈거냐가 고민이었다.
4. 예를들어 기준점에서 우측과 아래에 배추가 심어져 있다면, 현재 상태를 문 상태에서 우측으로 나아가다 어떻게 다시 기준점으로 와서 밑으로 이어질거며, 우측으로 나아가던 중간에 또 아래로 이어지는 지점이 나오면 거기는 또 어떻게 기억을 해두었다가 밑으로 이어질 것인지를 고민하였다.
5. 그러다가 재귀함수를 사용하면 계속하여 상태를 이어나가면서 나중에 어떤 지점까지 이르러서 모두 회수하여 회수된 상태로 무언가를 판단할 수 있지 않을까란 생각에 재귀함수를 사용하여 문제를 풀어보기로 하였다.

• 성공
• 메모리 : 16024 KB
• 시간 : 160 ms

보안점

1. 다른사람의 풀이를 참고하였는데,
2. 이차배열을 int형으로 하였는데 boolean 타입으로 하고 true, false의 형태로 처리 하였으면 메모리 효율이 더 좋지 않았을까란 생각을 하였다.
3. 또한 호출 메소드에서 좌 우 위 아래를 각각 표현하다보니 중복된 코드의 사용이 있었는데, 가로와 세로에 관해 (0, 1, -1)의 배열을 각각 만들고, 4번 반복되는 for문을 이용하여 처리하여 하나의 코드로 처리하는 것도 참고하여야겠다.