[BOJ]白準1012号有機白菜(Python)

質問する

入力

しゅつりょく

例

入力します。

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

出力します。

5
1

入力します。

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

出力します。

2

に答える

# 좌표를 움직일때 사용할 리스트
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# DFS. 모여있는 배추끼리 체크할 때.
def dfs(x, y):
    global M, N, K, ch, matrix
	
    ch[y][x] = 1		# 현재 위치 체크
    for d in range(4):		# 붙어있는 배추 있는지 확인
        nx = x + dx[d]		# 다음 x좌표
        ny = y + dy[d]		# 다음 y좌표
	# 다음 좌표가 유효한 좌표인지, 배추가 있는지, 지나온 곳은 아닌지 확인
        if 0 <= nx < M and 0 <= ny < N and matrix[ny][nx] == 1 and ch[ny][nx] == 0:
            dfs(nx, ny)		# 다음 좌표로 이동

# 풀이
def solution():
    global M, N, K, ch, matrix
    M, N, K = map(int, input().split())
    matrix = list([0 for _ in range(M)] for _ in range(N))	# 지도
    ch = list([0 for _ in range(M)] for _ in range(N))		# 지나온 곳인지 확인 용도
    cnt = 0			# 필요한 배추흰지렁이 개수
    if K > M * N - (min(M, N)):	# recursion 런타임 에러 방지
        return 1
        
    # 배추 위치 표시
    for i in range(K):
        x, y = map(int, input().split())
        matrix[y][x] = 1
    
    # 배추 위치 확인
    for r in range(N):		# row
        for c in range(M):	# column
            # 배추 위치 확인하고 이미 체크한 곳도 아니면 cnt 1 증가, dfs 실행
            if matrix[r][c] == 1 and ch[r][c] == 0:
                cnt += 1
                dfs(c, r)

    return cnt

# 메인함수
if __name__ == "__main__":

    T = int(input())
    for _ in range(T):
        print(solution())