[BOJ] 1012. 유기농배추 –

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

– 인접한 위치(위, 아래, 왼쪽, 오른쪽)는 한 위치로 계산됩니다. 따라서 시작 지점을 만났을 때 끝까지 검색하고 1로 계산하여 위치를 계산할 수 있습니다.

– 이미 카운트된 장소는 중복 검색하지 마시고 브라우징 시 반드시 방문한 것으로 표시하세요.

– 끝까지 검색 가능한 문제이므로 bfs 또는 dfs는 중요하지 않습니다. 나는 bfs를 사용했다.

– 0과 1의 배열을 읽어서 풀 수도 있지만 저는 좌표만 읽어서 주어진 좌표가 좌표 목록(석탄)에 있으면 이웃 위치로 간주하는 방식으로 문제를 풀었습니다.

– 배열만 구해서 풀면 더 좋았을 것 같아요.

전송 코드

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)

용해 과정