백준 - 유기농 배추

▶문제

 

 

 

▶풀이

이 문제는 연속된 배추 영역의 개수를 구하면 되는 문제이다.

연속된 영역의 개수는 자료구조 시간에 이미 BFS, DFS 방식으로 배웠다.

 

나는 두 방식 중 BFS(너비 우선 탐색) 방식으로 문제를 풀었다.

• 방문한 배추는 더 이상 탐색되지 않도록 0으로 변경해 처리
• 배추가 있는 위치(matrix[a][b] == 1)에서 BFS를 수행해 하나의 배추 그룹을 탐색하고 그룹의 개수를 증가

즉, 배추밭을 모두 순회하며 배추가 있는 새로운 그룹을 발견할 때마다 BFS로 해당 그룹을 모두 탐색하고, 그룹 카운트를 증가시킨다. 

 

전체 코드

T = int(input())  # 테스트 케이스 수 입력

dx = [-1, 1, 0, 0]  # 상하 이동
dy = [0, 0, -1, 1]  # 좌우 이동

def BFS(x, y):
    queue = [(x, y)]  # 탐색할 좌표를 담는 큐
    matrix[x][y] = 0  # 방문 처리

    while queue:
        x, y = queue.pop(0)  # 큐에서 좌표를 꺼냄

        for i in range(4):  # 상하좌우 탐색
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx >= M or ny < 0 or ny >= N:  # 범위 밖이면 패스
                continue

            if matrix[nx][ny] == 1:  # 배추가 있으면
                queue.append((nx, ny))  # 큐에 추가
                matrix[nx][ny] = 0  # 방문 처리

# 각 테스트 케이스에 대한 처리
for _ in range(T):
    M, N, K = map(int, input().split())  # 밭의 크기 M, N과 배추 수 K 입력
    matrix = [[0] * N for _ in range(M)]  # 배추밭 초기화
    group_count = 0  # 배추 그룹 수

    for _ in range(K):
        x, y = map(int, input().split())  # 배추 좌표 입력
        matrix[x][y] = 1  # 배추 위치 설정

    for i in range(M):
        for j in range(N):
            if matrix[i][j] == 1:  # 새로운 배추 그룹 발견
                BFS(i, j)  # BFS 실행
                group_count += 1  # 그룹 수 증가

    print(group_count)  # 결과 출력

 

1. 이동 방향 정의

dx = [-1, 1, 0, 0]  # 상하 이동
dy = [0, 0, -1, 1]  # 좌우 이동

dx와 dy는 상하좌우로 이동할 때 좌표를 변경하는 값을 나타낸다. 

• dx: 세로 방향(위로 -1, 아래로 +1) 이동.
• dy: 가로 방향(왼쪽으로 -1, 오른쪽으로 +1) 이동

2. BFS 함수

def BFS(x, y):
    queue = [(x, y)]  # 탐색할 좌표를 저장하는 큐
    matrix[x][y] = 0  # 현재 배추를 방문 처리

    while queue:
        x, y = queue.pop(0)  # 큐에서 좌표를 꺼냄

        for i in range(4):  # 상하좌우 탐색
            nx = x + dx[i]  # 새로운 x 좌표 계산
            ny = y + dy[i]  # 새로운 y 좌표 계산

            if nx < 0 or nx >= M or ny < 0 or ny >= N:  # 범위를 벗어나면 무시
                continue

            if matrix[nx][ny] == 1:  # 인접한 배추가 있으면
                queue.append((nx, ny))  # 큐에 추가하여 탐색을 이어감
                matrix[nx][ny] = 0  # 방문 처리 (배추를 없앰)

 

• 주어진 배추 좌표에서 시작하여 상하좌우로 인접한 배추를 모두 탐색하고, 방문한 배추는 0으로 변경하여 방문 처리
• 현재 탐색할 좌표를 저장하는 큐
• matrix[x][y] = 0: 현재 좌표의 배추를 방문 처리하여 다시 방문하지 않도록 한다. 
• 4방향 탐색: 상하좌우로 배추가 인접해 있는지 확인하고, 인접한 배추가 있으면 큐에 추가하여 계속 탐색한다.

3. 테스트 케이스 처리

for _ in range(T):
    M, N, K = map(int, input().split())  # 가로 M, 세로 N, 배추의 개수 K 입력
    matrix = [[0] * N for _ in range(M)]  # M x N 크기의 배추밭 초기화
    group_count = 0  # 배추 그룹의 개수를 세는 변수

    for _ in range(K):
        x, y = map(int, input().split())  # 배추가 심어진 좌표 입력
        matrix[x][y] = 1  # 해당 좌표에 배추가 있음을 표시

 

 

4. 배추밭 순회 및 BFS 실행

    for i in range(M):
        for j in range(N):
            if matrix[i][j] == 1:  # 새로운 배추 그룹 발견
                BFS(i, j)  # BFS로 해당 그룹 탐색
                group_count += 1  # 그룹 수 증가

 

• 이중 반복문으로 배추밭을 순회하면서 배추가 있는 위치를 찾는다.
• 배추가 있는 좌표(matrix[i][j] == 1)에서 BFS를 실행하여 해당 그룹의 모든 배추를 탐색한다. 
• 새로운 배추 그룹을 찾으면 group_count를 1 증가시킨다.