-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
안녕하세요. 궁금한점이 있어서 질문드립니다.
23.08.09 07:24 작성 조회수 136
0
안녕하세요. 궁금한점이 있어서 질문드립니다.
BFS를 풀다가 생각난건데
OOOXX
XXOOO
OXXXX
XXXXX
OOOOO
이렇게 배열이 들어왔을때
11122
33111
43333
33333
55555
이런식으로 영역별로 숫자가 1씩 증가되는
코드를 작성하고 싶은데 어떻게 해야할까요..?
답변을 작성해보세요.
1
인프런 AI 인턴
2023.08.11
안녕하세요, 인프런 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]
이렇게 숫자가 증가된 결과를 얻으실 수 있습니다. 원하는 출력 형태에 맞게 수정하여 사용하시면 됩니다.
더 좋은 방법이 있다면, 지식 공유자분들께서 추가로 답변해주시면 감사하겠습니다.
답변 1