[Java] 백준 25565번 딸기와 토마토

토마토와 딸기를 심을 때 겹쳐서 심게된 곳의 개수와 위치를 출력하는 문제입니다.
2명의 사람이 연속해서 K개를 심었는데 어떤부분이 겹쳐져있는지 찾아야합니다.

입력을 받고 배열에 저장할 때 1의 개수를 세어 주었습니다.
K * 2 - (1의 개수)를 해주면 겹쳐서 심어져있는 수를 알 수 있습니다.

총 3가지 경우로 구분하였습니다. (cnt = 겹쳐진 개수)
1. cnt == K
2. cnt == 1
3. cnt > 1

1번의 경우
겹쳐진 수와 K가 같다는건 두 사람 모두 같은곳에 심었다는 것을 의미합니다.
반복문을 통해서 1이 있는 곳들의 위치를 모두 출력해 주었습니다.

2번의 경우 
토마토와 딸기가 크로스 모양(세로, 가로)로 하나가 겹쳐있는 상태와
( TTOSS ) 토마토와 딸기가 직선으로 하나만 겹쳐 있는 경우가 가능합니다.

먼저 크로스 모양으로 되어있는 경우를 판단해줍니다.
모든 위치를 탐색해서 세로와 가로가 모두 존재하는 곳을 출력해주었습니다.
cnt가 1이므로 찾은 위치가 유일합니다.

위의 경우를 다 확인했을 때 찾지 못한 경우 토마토와 딸기가 직선으로 하나만 겹쳐있는 경우입니다.
이 경우는 3번의 경우에서 찾는 방식과 동일하므로 3번의 함수를 호출해주었습니다.

3번의 경우
토마토와 딸기가 일직선 상에 겹쳐서 존재하는 경우입니다.
1이 나온경우 연속하여 K까지 탐색합니다.
이 때 뒤에 cnt만큼 겹쳐있는것이므로 해당 부분을 출력해주었습니다.

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

public class Main {
  static int n;

  static int m;
  static int k;
  static int cnt;
  static int[][] map;
  static ArrayList<Pair> al;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    n = Integer.parseInt(st.nextToken());
    m = Integer.parseInt(st.nextToken());
    k = Integer.parseInt(st.nextToken());
    cnt = 0;
    map = new int[n][m];
    al = new ArrayList<>();

    for (int i = 0; i < n; ++i) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < m; ++j) {
        map[i][j] = Integer.parseInt(st.nextToken());
        if (map[i][j] == 1) {
          ++cnt;
        }
      }
    }

    cnt = k * 2 - cnt;

    if (cnt == k) {
      func1();
    } else if (cnt == 1) {
      func2();
    } else if (cnt > 1) {
      func3();
    }

    bw.write(cnt + "\n");
    for (int i = 0; i < al.size(); ++i) {
      bw.write((al.get(i).y + 1) + " " + (al.get(i).x + 1) + "\n");
    }

    bw.close();
  }

  public static void func1() {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (map[i][j] == 1) {
          boolean chk = false;

          al.add(new Pair(i, j));
          if (j + 1 < m && map[i][j + 1] == 1) {
            chk = false;
          } else if (i + 1 < n && map[i + 1][j] == 1) {
            chk = true;
          }
          for (int l = 1; l < k; ++l) {
            if (chk) {
              al.add(new Pair(i + l, j));
            } else {
              al.add(new Pair(i, j + l));
            }
          }

          return;
        }
      }
    }
  }

  public static void func2() {
    int[] my = { 0, 0, 1, -1 };
    int[] mx = { 1, -1, 0, 0 };

    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (map[i][j] == 1) {
          int c = 0;
          for (int k = 0; k < 4; ++k) {
            int nextY = i + my[k];
            int nextX = j + mx[k];

            if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= m || map[nextY][nextX] == 0) {
              continue;
            }

            if (k < 2) {
              c |= 1;
            } else {
              c |= 2;
            }
          }

          if (c == 3) {
            al.add(new Pair(i, j));
            return;
          }
        }
      }
    }
    func3();
  }

  public static void func3() {
    int c = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < m; ++j) {
        if (map[i][j] == 1) {
          boolean chk = false;

          ++c;
          if (j + 1 < m && map[i][j + 1] == 1) {
            chk = false;
          } else if (i + 1 < n && map[i + 1][j] == 1) {
            chk = true;
          }
          for (int l = 1; l < k; ++l) {
            if (chk) {
              if (k - c <= cnt) {
                al.add(new Pair(i + l, j));
              }
              ++c;
            } else {
              if (k - c <= cnt) {
                al.add(new Pair(i, j + l));
              }
              ++c;
            }
          }

          return;
        }
      }
    }
  }

  public static class Pair {
    int y;
    int x;

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