[백준 25565] 딸기와 토마토 (Implementation, 파이썬3)

딸기와 토마토

문제

즈티와 레오가 사는 집 앞마당에는 $N\times M$ 크기의 작은 텃밭이 있다. 텃밭의 좌측 상단의 좌표는 $(1, 1)$이며, 우측 하단의 좌표는 $(N, M)$이다. 텅 빈 텃밭이 허전해 보인 둘은 각자 원하는 작물을 텃밭에 심고 예쁘게 키워보기로 했다. 즈티는 $K$칸 이상인 가로 또는 세로 줄 하나를 고른 후 그 줄에서 임의의 연속한 $K$개의 칸에 모두 딸기 씨앗을 심었고, 레오는 같은 방법으로 토마토 씨앗을 심었다. 텃밭을 벗어나서 씨앗을 심을 수는 없다. 텃밭의 각 칸에 종류와 상관없이 씨앗이 존재하는지가 주어질 때, 딸기와 토마토가 같이 자랄 칸의 좌표를 전부 구해보자. 단, 씨앗에서 작물이 자라지 않는 경우는 없으며, 조건에 맞는 입력만 주어진다.

입력
첫 번째 줄에 $N, M, K$가 공백으로 구분되어 주어진다. $(1 \le N,M \le 2\,000, 1 \le K \le \max(N,M))$ 

두 번째 줄부터 $N$개의 줄에 각 칸의 씨앗 존재 여부를 나타내는 $M$개의 정수가 공백으로 구분되어 주어진다. $1$은 씨앗이 존재한다는 것, $0$은 존재하지 않는다는 것을 의미한다.

출력
첫 번째 줄에 딸기와 토마토가 같이 자랄 칸의 수를 출력한다.

딸기와 토마토가 같이 자랄 칸이 한 개 이상이라면, 두 번째 줄부터 한 줄에 하나씩 딸기와 토마토가 같이 자랄 칸의 좌표를 첫 번째 좌표가 증가하는 순으로, 첫 번째 좌표가 같으면 두 번째 좌표가 증가하는 순으로 출력한다.

풀이

딸기와 토마토가 같이 자라는 칸의 수를 출력한다.

같이 자라는 칸이 없다면 바로 종료한다.

---

같이 자라는 칸이 한 칸이라면

1. 수직으로 놓여서 한 칸만 겹치는 경우와
2. 수평으로 놓였지만 1칸만 겹치는 경우가 있다.

값이 1인 칸을 bfs 탐색하며 방향이 바뀌는 위치를 찾는다.

방향이 바뀌는 위치가 바로 딸기와 토마토가 같이 자라는 칸이므로 해당 위치를 출력하고 종료한다.

탐색이 끝나도 방향이 바뀌는 칸이 없다면 수평이라는 의미이다.
k*2-1개의 1 중 가운데 값을 출력한다.

---

같이 자라는 칸이 두 칸 이상이라면, 수평으로 놓인 경우밖에 없다.

시작 위치에서 (k-cnt)만큼 떨어진 위치부터 cnt개의 좌표를 출력한다.

이때, 시작 위치를 왼쪽 위에서부터 탐색하므로 무조건 정렬된 순서로 출력이 된다.

코드

from collections import deque

n, m, k = map(int, input().split())
board = list(list(map(int, input().split())) for _ in range(n))

# cnt : 딸기와 토마토가 같이 자랄 칸의 수
cnt = k*2 - sum([1 if board[i][j] == 1 else 0 for i in range(n) for j in range(m)]) 
print(cnt)          # 칸 수 출력
if cnt == 0: exit() # 겹치지 않으면 종료
    
dxy = [[0, -1], [0, 1], [-1, 0], [1, 0]]

def find1():
    for x in range(n):
        for y in range(m):
            if board[x][y] == 0: continue

            queue = deque([(x, y)])
            board[x][y] = 2
            dir = -1	# 수평일 경우를 위해 방향 저장
            while queue:	# bfs 탐색
                cx, cy = queue.popleft()
                for d in range(4):
                    nx, ny = cx + dxy[d][0], cy + dxy[d][1]
                    if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
                    if board[nx][ny] == 0: continue
                    
                    if board[nx][ny] == 1:
                        queue.append((nx, ny))
                        board[nx][ny] = 2	# 방문 체크
                        
                    if dir == -1: dir = d
                    elif ((dir == 0 or dir == 1) and (d == 2 or d == 3)) or ((dir == 2 or dir == 3) and (d == 0 or d == 1)):	# 방향이 바뀌는 위치
                        print(cx+1, cy+1)
                        return()

            # bfs가 종료되면 수평으로 놓였다는 의미이므로 중간값 출력
            print(x+dxy[dir][0]*(k-1)+1, y+dxy[dir][1]*(k-1)+1)
            return()
            

def find2():
    for x in range(n):
        for y in range(m):
            if board[x][y] == 0: continue
            
			# 방향 찾기
            dir = -1
            for d in range(4):
                nx, ny = x + dxy[d][0], y + dxy[d][1]
                if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
                if board[nx][ny] == 0: continue
                dir = d
                break
            
			# 시작 위치에서 k-cnt만큼 떨어진 위치에서부터 좌표 출력
            sx, sy = x + dxy[dir][0]*(k-cnt)+1, y + dxy[dir][1]*(k-cnt)+1
            for _ in range(cnt):	# cnt개의 좌표
                print(sx, sy)
                sx, sy = sx + dxy[dir][0], sy + dxy[dir][1]
            return()
                
if cnt == 1: find1()	# 1개의 좌표 찾기
else: find2()			# 2개 이상의 좌표 찾기