[Baekjoon] 딸기와 토마토

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

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

public class Main {
    static StringBuilder answer = new StringBuilder();
    static int N, M, K, oneCount;
    static int[] yCount, xCount;

    public static void main(String[] args) throws Exception {
        init();
        sol();
        print();
    }

    static void sol() {
        if (oneCount == 2 * K) {
            // K의 2배만큼 1이 존재할 경우, 겹치지 않는다는 뜻
            answer.append("0");
            return;
        }

        int rowWithK = -1, colWithK = -1;
        int firstRow = -1, lastRow = -1;
        int firstCol = -1, lastCol = -1;

        for (int i = 1; i <= N; i++) {
            if (xCount[i] > 0) {
                if (firstRow == -1)
                    firstRow = i;
                lastRow = i;
            }
            if (xCount[i] >= K)
                rowWithK = i;
        }

        for (int j = 1; j <= M; j++) {
            if (yCount[j] > 0) {
                if (firstCol == -1)
                    firstCol = j;
                lastCol = j;
            }
            if (yCount[j] >= K)
                colWithK = j;
        }

        // 교차점이 존재하는 경우
        if (rowWithK != -1 && colWithK != -1) {
            answer.append("1\n").append(rowWithK).append(" ").append(colWithK);
            return;
        }

        int duplicateCount = 2 * K - oneCount;
        answer.append(duplicateCount).append("\n");

        // 둘 다 같은 열에 있는 경우
        if (colWithK != -1) {
            int startRow = firstRow + (K - duplicateCount);
            int endRow = lastRow - (K - duplicateCount);
            for (int i = startRow; i <= endRow; i++) {
                answer.append(i).append(" ").append(colWithK).append("\n");
            }
        }
        // 둘 다 같은 행에 있는 경우
        else {
            int startCol = firstCol + (K - duplicateCount);
            int endCol = lastCol - (K - duplicateCount);
            for (int j = startCol; j <= endCol; j++) {
                answer.append(rowWithK).append(" ").append(j).append("\n");
            }
        }
    }

    static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        yCount = new int[M + 1];
        xCount = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                int value = Integer.parseInt(st.nextToken());

                if (value == 1) {
                    oneCount++;
                    yCount[j]++;
                    xCount[i]++;
                }
            }
        }
    }

    static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(answer));
        bw.close();
    }
}

주요 개념

• 구현

풀이 방법

• 처음 보았을 때, DFS를 떠올렸으나 2차원 배열이 최대 2000*2000 까지 되었기 때문에 비효율적이라고 생각했다.

• 이후, 각 행과 열에서의 1의 갯수를 저장하고 이를 활용하면 빠르게 구현할 수 있다.

  • 아래는 각 예시다.

    // yCount = 0311
    // xCount = 131 인 경우
    // -> 2,2 가 교차점
    
    // yCount = 21
    // xCount = 12 인 경우
    // -> 1,2 가 교차점
    
    // yCount = 030
    // xCount = 111
    // -> 모두 겹침
    
    // yCount = 11111
    // xCount = 5
    // K = 3 -> 1,3 겹침
    // k = 4 -> 1,2 1,3 1,4 겹침
    
    // 1) 각 축에 K값이 존재하면 하나만 겹침
    // 2) 한 축에만 K값이 존재하면 모두 겹침
    // 3) 각 축에 K값이 없다면 2개 이상 겹침

  • 해당 예시는 상단에 2*K == oneCount로 겹치지 않는 경우의 수를 모두 제거했을 때 유효하다.

  • 1번 예시와 2&3번 예시를 처리하는 로직을 구현하면 된다.