[코딩인터뷰] 백준 2468번

백준 2468번

Python 으로 DFS 전략으로 풀면 'Recursion Error' 나고 '메모리 초과' 나고 난리납니다. 그래서 BFS 로 바꿔서 풀어야 합니다. 전에는 DFS 가능했는데 메모리가 줄었나 봅니다.

BFS

from collections import deque

# 2 <= n <= 100 / 1 <= h <= 100
n = int(input())
maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

answer = 1
for level in range(1, 101):

    count = 0
    visited = [[False] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if level < maps[i][j] and not visited[i][j]:
                q = deque()
                visited[i][j] = True
                q.append((i,j))

                while q:
                    x, y = q.popleft()

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]

                        if 0 <= nx < n and 0 <= ny < n:
                            if level < maps[nx][ny] and not visited[nx][ny]:
                                visited[nx][ny] = True
                                q.append((nx, ny))

                count += 1

    if count == 0:
        break
    elif answer < count:
        answer = count

print(answer)

DFS

import sys
sys.setrecursionlimit(100000)

def dfs(level, x, y):
    global n, maps, visited, dx, dy

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < n and 0 <= ny < n:
            if level < maps[nx][ny] and not visited[nx][ny]:
                visited[x][y] = True
                dfs(level, nx, ny)

# 2 <= n <= 100 / 1 <= h <= 100
n = int(input())
maps = []
for _ in range(n):
    maps.append(list(map(int, input().split())))

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

answer = 1
for level in range(1, 101):

    count = 0
    visited = [[False] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if maps[i][j] > level and not visited[i][j]:
                visited[i][j]
                dfs(level, i, j)
                count += 1

    if answer < count:
        answer = count

    if count == 0:
        break

print(answer)