[BOJ] 1012. 유기농배추 - 파이썬

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

1012번: 유기농 배추

 

아이디어
1. 인접한 곳(상하좌우)면 한 곳으로 치니까 출발점을 만나면 끝까지 탐색해 1을 카운트해주면 한 곳을 셀 수 있다.
2. 이미 카운트한 곳은 중복으로 탐색하면 안되므로 탐색할때 방문 표시를 해둬야한다.
- 끝까지 탐색하면 되는 문제이므로 bfs,dfs 든 관계없다. 나는 bfs를 이용했다.
- 0과1로 된 배열을 읽어와 풀어도 되는데, 나는 그냥 좌표만 읽어와서, 특정 좌표가 좌표 리스트(cabbages)에 있으면 인접한 곳으로 간주하는 식으로 문제를 풀었다.

 

>> 제출 코드

T = int(input())

for _ in range(T):
    M,N,K = map(int,input().split())
    cabbages = []
    for _ in range(K):
        i,j = map(int,input().split())
        cabbages.append((i,j))
    di = [-1,0,1,0]
    dj = [0,1,0,-1]
    checked = []
    cnt = 0

    for cabbage in cabbages:  # 각 좌표를 순회하면서 너비탐색할 예정
        if cabbage in checked:  # 이미 체크한 좌표면 너비탐색할 필요없이 넘어감
            continue
        else:
            checked.append(cabbage)  #  먼저 좌표에 확인 표시를 하고
            Q = [cabbage]  # 큐를 만들어 좌표를 넣음
            while Q:  # 큐에 좌표가 있는 한 계속 반복
                now = Q.pop(0)
                for k in range(4):  # 인접리스트 대신 델타 탐색
                    ni = now[0] + di[k]
                    nj = now[1] + dj[k]
                    if not (ni,nj) in checked and (ni,nj) in cabbages:
                        checked.append((ni,nj))
                        Q.append((ni,nj))
            cnt += 1

    print(cnt)

풀이 과정