인프런 커뮤니티 질문&답변

안녕하세요, 인프런 AI인턴이에요.

주어진 배열에 대해서 영역별로 숫자가 1씩 증가되는 코드를 작성하고 싶으시다면 BFS 알고리즘을 사용하시면 될 것 같습니다. 영역별로 숫자를 증가시킬 때, BFS를 사용하게 되면 각 영역의 크기에 따라 숫자를 증가시킬 수 있습니다.

하나의 접근 방식을 소개해드리겠습니다. 우선, 배열의 크기에 맞게 방문 체크 배열을 생성하고, BFS를 사용하여 각 영역의 크기를 파악한 후, 숫자를 증가시킬 수 있습니다.

아래는 작성한 코드 예시입니다.

from collections import deque

def bfs(arr, visited, x, y, num):
    dx = [-1, 1, 0, 0]  # 상하좌우 이동을 위한 dx, dy
    dy = [0, 0, -1, 1]  
    q = deque([(x, y)])
    visited[x][y] = True
    arr[x][y] = num

    while q:
        cur_x, cur_y = q.popleft()

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if 0 <= next_x < len(arr) and 0 <= next_y < len(arr[0]) and not visited[next_x][next_y] and arr[next_x][next_y] == 'O':
                q.append((next_x, next_y))
                visited[next_x][next_y] = True
                arr[next_x][next_y] = num

def increaseAreaNumber(arr):
    num = 1  # 영역별 숫자
    visited = [[False] * len(arr[0]) for _ in range(len(arr))]

    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if not visited[i][j] and arr[i][j] == 'O':
                bfs(arr, visited, i, j, num)
                num += 1

    return arr

arr = [
    ['O', 'O', 'O', 'X', 'X', 'X', 'X', 'O', 'O', 'O'],
    ['O', 'O', 'O', 'O', 'X', 'X', 'X', 'O', 'O', 'O'],
    ['O', 'O', 'O', 'O', 'X', 'X', 'X', 'X', 'X', 'X'],
    ['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
    ['O', 'O', 'O', 'O', 'O', 'X', 'X', 'X', 'X', 'X'],
    ['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O']
]

result = increaseAreaNumber(arr)
for row in result:
    print(row)

위의 코드는 입력된 배열에서 ‘O’에 해당하는 영역을 탐색하고, 해당 영역에 대해 숫자를 증가시키는 코드입니다.

실행 결과는 다음과 같습니다.

[1, 1, 1, 'X', 'X', 'X', 'X', 2, 2, 2]
[1, 1, 1, 1, 'X', 'X', 'X', 2, 2, 2]
[1, 1, 1, 1, 'X', 'X', 'X', 'X', 'X', 'X']
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 1, 1, 1, 1, 'X', 'X', 'X', 'X', 'X']
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

이렇게 숫자가 증가된 결과를 얻으실 수 있습니다. 원하는 출력 형태에 맞게 수정하여 사용하시면 됩니다.

더 좋은 방법이 있다면, 지식 공유자분들께서 추가로 답변해주시면 감사하겠습니다.