[코드트리 파이썬] 뿌요뿌요

문제

---

풀이

동일한 숫자를 가진 블럭을 찾아야하므로 DFS를 이용하였다.

 

def dfs(r, c, now):
    global cnt, maxValue
    visited[r][c] = True
    cnt += 1
    now = graph[r][c]
    for i in range(4):
        nr, nc = dr[i] + r, dc[i] + c
        if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and graph[nr][nc] == now:
            dfs(nr, nc, now)

    if cnt >= 4:
        return True
    else:
        return False

DFS의 구현은 다음과 같다.

이 문제에서 중요한 점은 같은 숫자를 가진 블럭이 4개 이상 되었을 때만 터진다는 점이다.

따라서 카운트를 해주기위해 전역변수 cnt를 선언하였다.

 

기본적으로 탐색은 DFS와 동일하게 진행된다.

범위에 벗어나지 않고, 방문하지 않았으며, 이전과 동일한 숫자를 가지고있으면 DFS를 재귀하여 탐색한다.

재귀 시 cnt값을 증가시켜 카운트를 올려준다.

탐색을 완료하고 cnt값이 4이상이면 True를 그렇지 않으면 False를 반환한다.

 

 

 

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            cnt = 0
            if dfs(i, j, 0):
                maxValue = max(maxValue, cnt)
                areaCnt += 1
            else:
                maxValue = max(maxValue, cnt)

탐색을 시작하는 코드이다.

격자의 개수만큼 탐색하되 방문하지 않았을경우만 탐색한다.

탐색 시 cnt 값은 0으로 초기화한다.

탐색 후 반환값이 True인 경우 터질 수 있는 블럭이 늘어난 경우이므로 areaCnt를 1증가시키고 maxValue값을 증가시킨다.

 

코드

n = int(input())

graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
dr = [-1, 1, 0, 0]
dc = [0, 0, 1, -1]

def dfs(r, c, now):
    global cnt, maxValue
    visited[r][c] = True
    cnt += 1
    now = graph[r][c]
    for i in range(4):
        nr, nc = dr[i] + r, dc[i] + c
        if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and graph[nr][nc] == now:
            dfs(nr, nc, now)

    if cnt >= 4:
        return True
    else:
        return False

maxValue = -1
areaCnt = 0

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            cnt = 0
            if dfs(i, j, 0):
                maxValue = max(maxValue, cnt)
                areaCnt += 1
            else:
                maxValue = max(maxValue, cnt)

print(areaCnt, maxValue)