[코드트리 챌린지] (5주차) DFS/안전지대

문제:

문제 링크: https://www.codetree.ai/missions/2/problems/comfort-zone?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

풀이: 저번주에 풀었던 마을 인원수 구하는 문제랑 비슷하게 풀었고, 그 문제보다 조금 더 쉬운 것 같다. 그런데 계속 maximum recursion error가 나서 토론탭에 봤더니 sys.setrecursionlimit()으로 늘려보라고 되어있었다. 늘렸더니 성공 ㅋㅋ

 

import sys
sys.setrecursionlimit(10**7)
n, m = tuple(map(int, input().split()))
vill = [
    list(map(int, input().split()))
    for _ in range(n)
]
visited = [[False]*m for _ in range(n)]
flooded = [[False]*m for _ in range(n)]

def can_go(i, j):
    if i < 0 or j < 0 or i >= n or j >= m: return False
    if visited[i][j]: return False
    if flooded[i][j]: return False
    return True

ks = [0]*(max(map(max, vill))+1) # k값별 안전지대 갯수 

def flooding(k):
    for i in range(n):
        for j in range(m):
            if vill[i][j] <= k:
                flooded[i][j] = True
            else: flooded[i][j] = False

dxs = [0, -1, 0, 1]
dys = [-1, 0, 1, 0]

def dfs(x, y):
    for dx, dy in zip(dxs, dys):
        nx = x + dx
        ny = y + dy
        if can_go(nx, ny):
            visited[nx][ny] = True
            dfs(nx, ny)


for k in range(1, len(ks)):
    flooding(k)
    visited = [[False]*m for _ in range(n)]

    for x in range(n):
        for y in range(m):
            if can_go(x, y):
                visited[x][y] = True
                dfs(x, y)
                ks[k] += 1

f = lambda i: ks[i]
k = max(range(1, len(ks)), key=f)
print(k, ks[k])

---

실력진단:

좀 올랐는데 그.. 퍼뮤테이션 구하는 문제를 그냥 함수 임포트해서 써가지고.. 그리고 다음문제는 오늘 주구장창 푼 dfs 문제라서.. 암튼 다음주엔 dp랑 퍼뮤테이션 문제를 공부하고 테스트 보겠다.