2019.03.11) 백준 dfs 특집 3편 - 11724, 2468(PyPy3)

dfs. 재밌다

해결하는 방법을 생각하고 짜면 바로 성공해서 맛이 난다.

11724번

c, n = map(int, input().split(' '))
# 그래프 제작
graph = {i: list() for i in range(1, c + 1)}
 
for i in range(n):
    a, b = map(int, input().split(' '))
    graph[a].append(b)
    graph[b].append(a)
 
visited = [False for i in range(c + 1)]
count = 0
 
# 모든 정점을 순환
for j in range(1, c + 1):
    # 물론 방문하지 않은 경우만
    if not visited[j]:
        stack = [j]
 
        while stack:
            now = stack.pop()
            visited[now] = True
 
            for i in graph[now]:
                if not visited[i]:
                    stack.append(i)
 
        count += 1
 
print(count)

2468번

c = int(input())
 
l = [list(map(int, input().split(' '))) for i in range(c)]
 
# 0부터 최대값까지 탐색해보기 위해 구함
m = 0
for i in range(c):
    for j in range(c):
        m = max(m, l[i][j])
 
# 결과값
mx = 0
 
# 0부터 최대값까지 탐색
for k in range(m + 1):
    visited = [[False for j in range(c)] for i in range(c)]
    n = 0
    for i in range(c):
        for j in range(c):
            if not visited[i][j]:
                # 만약 탐색중인 수보다 크면 DFS
                if l[i][j] > k:
                    stack = [(i, j)]
                    # 대피소? 영역 1씩 추가
                    n += 1
                    while stack:
                        a, b = stack.pop()
                        visited[a][b] = True
                        if a > 0 and not visited[a - 1][b] and l[a - 1][b] > k:
                            stack.append((a - 1, b))
                        if b > 0 and not visited[a][b - 1] and l[a][b - 1] > k:
                            stack.append((a, b - 1))
                        if a < c - 1 and not visited[a + 1][b] and l[a + 1][b] > k:
                            stack.append((a + 1, b))
                        if b < c - 1 and not visited[a][b + 1] and l[a][b + 1] > k:
                            stack.append((a, b + 1))
 
                else:
                    visited[i][j] = True
 
    mx = max(mx, n)
 
print(mx)