[오답노트/파이썬] 코드업 - 캔디팡

문제

풀지 못한 이유

• BFS 알고리즘을 이용하여 현재 칸에서 상하좌우로 같은 색의 칸이 있는지 확인해 보려고 했으나, 현재 칸과 같은 칸들의 묶음을 어떻게 카운팅 해야 할지 몰랐다.

풀이

BFS 알고리즘을 이용하여 현재 칸을 기준으로 상하좌우를 확인하고 동일한 색이 있으면 다시 그 칸을 기준으로 상하좌우를 확인한다. 이렇게 카운팅 한 칸이 3개 이상이면 터지는 영역으로 간주한다.

board = []
for _ in range(7):
    board.append(list(map(int, input().split())))

from collections import deque

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

def bfs(x, y, board, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True    # 방문 처리

    color = board[x][y]    # 현재 칸의 색상
    count = 1    # 같은 색의 칸 개수

    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()

        # 현재 칸에서 상하좌우 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 보드 넘어서면 무시하기
            if nx < 0 or nx >= 7 or ny < 0 or ny >= 7:
                continue

            # 칸의 색상이 동일하고 방문한 적 없으면 재귀 (그 칸을 기준으로 다시 상하좌우 확인)
            if board[nx][ny] == color and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True    # 방문처리
                count += 1

    # 색상이 같은 부분이 3개 이상이면
    if count >= 3:
        return True
    else:
        return False

visited = [[False for _ in range(7) ] for _ in range(7)]    # 방문 여부
res = 0    # 터지는 영역의 개수

for i in range(7):
    for j in range(7):
        if not visited[i][j]:
            if bfs(i, j, board, visited):
                res += 1

print(res)

위의 코드를 찬찬히 살펴보자.
먼저, BFS 알고리즘을 이용하기 위해서 deque를 import 한다. 그리고 상하좌우에 위치한 칸을 확인하기 위해서 좌표를 미리 정의해둔다.

from collections import deque

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

그다음 제일 아랫부분부터 살펴보면 각 칸의 방문 여부를 기록할 2차원 리스트 visited와 최종적으로 터지는 영역의 개수를 담을 res 변수를 선언한다.
2중 for 문으로 각 칸을 확인할 거다. bfs 함수의 결과는 True or False인데, 동일한 색의 칸이 3개 이상이면 True를, 아니면 False를 반환한다.

visited = [[False for _ in range(7) ] for _ in range(7)]    # 방문 여부
res = 0    # 터지는 영역의 개수

for i in range(7):
    for j in range(7):
        if not visited[i][j]:
            if bfs(i, j, board, visited):
                res += 1

print(res)

이제 bfs 함수를 살펴보자. 우선 현재 방문한 칸을 큐에 넣고 방문 여부를 True로 갱신한다. 그리고 현재 칸의 색상(color)과 같은 색의 칸 개수(count) 변수를 정의한다.

이제 큐가 빌 때까지 반복한다.
먼저, 현재 칸의 좌표(x, y)를 큐에서 꺼낸다. 이 좌표를 기준으로 상하좌우 칸을 확인하는데, 아직 방문한 적이 없고 색상이 동일한 칸일 때만 다시 그 칸을 기준으로 상하좌우를 확인하다.(count += 1)

이렇게 다 확인하고 나서 같은 색의 칸이 3개 이상이면 True를 반환하고 아니면 False를 반환하는 것이다.

def bfs(x, y, board, visited):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True    # 방문 처리

    color = board[x][y]    # 현재 칸의 색상
    count = 1    # 같은 색의 칸 개수

    # 큐가 빌 때까지 반복
    while queue:
        x, y = queue.popleft()

        # 현재 칸에서 상하좌우 확인
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            # 보드 넘어서면 무시하기
            if nx < 0 or nx >= 7 or ny < 0 or ny >= 7:
                continue

            # 칸의 색상이 동일하고 방문한 적 없으면 재귀 (그 칸을 기준으로 다시 상하좌우 확인)
            if board[nx][ny] == color and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True    # 방문처리
                count += 1

    # 색상이 같은 부분이 3개 이상이면
    if count >= 3:
        return True
    else:
        return False

회고

확실히 예전보단 BFS 알고리즘을 이용한 기본 코드(기초적인 코드)는 잘 작성하지만 아직 문제에 알맞은 코드를 작성하기엔 벅차다. 더 노력하자.