greentea31's Note

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

풀이 과정

직사각형 NxM 텃밭에 즈티가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 K개의 딸기를 심고, 레오가 가로 한 줄, 혹은 세로 한 줄을 지정해 임의의 연속한 토마토 K개를 심는다. 씨앗의 종류에 상관 없이 씨앗이 심어진 영역의 좌표가 주어질 때, 딸기와 토마토가 모두 자라는 텃밭 영역의 칸 수와 해당 칸수를 출력하는 문제이다.

텃밭에서 씨앗이 심겨진 칸의 개수를 seed라 하자. 그렇다면 2K - seed의 값이 딸기와 토마토가 같이 심어진 칸의 수임을 쉽게 유추할 수 있을 것이다. 이 경우에 아래의 3가지 경우를 고려할 수 있다.

1. 2K == seed

이 경우에는 딸기와 토마토가 어떠한 영역에도 같이 심어지지 않았을 것이다. 같이 심어졌으려면 seed가 2K보다는 적어야 한다. 그냥 0을 출력해주면 된다.

1.5. K == 1

2K == seed가 아니면서 K == 1이면 board를 살펴보다가 1이 나오는 순간 그 지점의 좌표를 출력해주면 된다.

2. 2K - 1 == seed

딸기와 토마토가 같이 심겨진 영역이 한 칸만 존재하는 경우이다. 딸기를 심는 영역과 토마토를 심는 영역이 가로, 세로 직선이 교차하면서 생기는 경우가 있는데, 그 경우에는 같이 심기는 공간이 1칸만 존재할 수 있고, 2K - 1 == seed일때 이러한 상황이 발생할 수 있다. 따라서 2K - 1일때 모든 칸에 대해 현재 칸에 씨앗이 심겨져 있고, 가로로 왼쪽 혹은 오른쪽에 씨앗이 존재하면서 세로로 위쪽 혹은 아래쪽에 씨앗이 존재하는 경우에는 교차하면서 같이 심기는 경우로 판단하여 한 칸의 좌표만 출력해주었다.

3. 2K - 1 >= seed

seed가 2K - 1보다 작거나, 2K - 1 == seed 인데 가로 세로 직선이 교차하면서 같이 심기는게 아닌 경우가 있다. 이 때는 딸기 영역과 토마토 영역이 가로 직선 - 가로 직선이 겹치거나, 세로 직선 - 세로 직선이 겹쳐서 같이 심기는 영역이 발생하는 경우이다. board를 확인하면서 가로-가로, 세로-세로 겹침중 어느 것인지 판단 후, 겹친 갯수와 겹친 부분을 출력해주면 된다. 겹친 부분은 겹치기 시작한 부분 + seed - K부터 1씩 늘려가면서 2K-S개를 세주면 구할 수 있다. 왜 이렇게 되는지 모르겠다면 코드를 참고하고 그림을 그려가며 생각해보자.

소스 코드

import sys


def one_check(b, N, M):
    dx = [1, -1]
    dy = [1, -1]
    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:
                continue
            check_x = False
            check_y = False
            for i in range(2):
                nx = x + dx[i]
                if 0 <= nx < M and board[y][nx] == 1:
                    check_x = True
                ny = y + dy[i]
                if 0 <= ny < N and board[ny][x] == 1:
                    check_y = True
            if check_x and check_y:
                return f'{y+1} {x+1}'

    return None


N, M, K = map(int, sys.stdin.readline().split())
board = []
for _ in range(N):
    board.append(list(map(int, sys.stdin.readline().split())))

seed = 0

for i in board:
    for j in i:
        if j == 1:
            seed += 1

if 2*K == seed:
    print(0)
    exit(0)

print(2*K - seed)

if K == 1:
    for y in range(N):
        for x in range(M):
            if board[y][x] == 1:
                print(f'{y+1} {x+1}') 
                exit(0)

if 2*K - 1 == seed:
    check = one_check(board, N, M)
    if check is not None:
        print(check)
        exit(0)

start_x, start_y = 2001, 2001
end_x, end_y = -1, -1

for y in range(N):
    for x in range(M):
        if board[y][x] == 1:
            start_x = min(x, start_x)
            start_y = min(y, start_y)
            end_x = max(x, end_x)
            end_y = max(y, end_y)

if start_x == end_x:
    for i in range(2*K - seed):
        print(f'{start_y + seed - K + i + 1} {start_x + 1}')
    exit(0)
if start_y == end_y:
    for i in range(2*K - seed):
        print(f'{start_y + 1} {start_x + seed - K + i + 1}')