[백준] 2468 파이썬(python) : 안전 영역 - (★)

2468번: 안전 영역

 

 

Python3로 제출해야 정답처리가 된다.

 

import sys
sys.setrecursionlimit(10**5)
n = int(sys.stdin.readline())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
max_value = max(map(max, graph))
min_value = min(map(min, graph))
dx = [ -1, 1, 0, 0 ]
dy = [ 0, 0, -1, 1 ]

def dfs(x, y, depth, visit):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if graph[nx][ny] > depth and not visit[nx][ny]:
                visit[nx][ny] = True
                dfs(nx, ny, depth, visit)
res = 1 #4
for i in range(1, max_value): #5
    cnt = 0
    visit = [ [False]*n for _ in range(n) ] #1
    for j in range(n):
        for k in range(n):
            if graph[j][k] > i and not visit[j][k]:
                visit[j][k] = True #2
                dfs(j, k, i, visit) #3
                cnt += 1
    res = max(res, cnt)
print(res)

 

#1 : 새로운 높이로 측정할때마다 visit을 새롭게 갱신

#2 : 처음위치는 방문처리, #1에서 다시 False로 갱신할거라서 괜찮다.

#3 : x좌표, y좌표, 깊이, 방문처리 배열을 인자로 넣어준다.

#4 : 힌트에서 아무 지역도 물에 잠기지 않을 수 있다 했으므로 res = 1로 설정

#5 : 높이는 1~100까지의 정수

 

이전에 풀었던 dfs문제에 약간의 변형을 준 문제인데 #1을 생각하지 못했다. 나는 아직 멀었다.

 

다른 dfs풀이 23.01.13(금)

import sys
sys.setrecursionlimit(10**5)
n = int(sys.stdin.readline())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
max_num = max(map(max, graph))

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

def dfs(x, y, depth):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == False:
            visit[nx][ny] = True
            dfs(nx, ny, depth)
arr = []
for i in range(1, max_num+1):
    visit = [ [False] *(n) for _ in range(n) ]
    for j in range(n):
        for k in range(n):
            if graph[j][k] < i: #1 잠기는 부분을 True로 한 뒤.(문제 조건에서 모두 안 잠길 수도 있으므로 '<')
                visit[j][k] = True
    count = 0
    for j in range(n):
        for k in range(n):
            if visit[j][k] == False:
                visit[j][k] = True
                dfs(j, k, i)
                count += 1
    arr.append(count)
print(max(arr))

 

비슷한 bfs풀이 23.01.13(금)

import sys
from collections import deque
n = int(sys.stdin.readline())
graph = [ list(map(int, sys.stdin.readline().split())) for _ in range(n) ]
max_num = max(map(max, graph))

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

def bfs(x, y, depth):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == False:
                visit[nx][ny] = True
                q.append((nx, ny))
arr = []
for i in range(1, max_num+1):
    visit = [ [False]*n for _ in range(n) ]
    for j in range(n):
        for k in range(n):
            if visit[j][k] == False and graph[j][k] < i:
                visit[j][k] = True
    count = 0
    for j in range(n):
        for k in range(n):
            if visit[j][k] == False:
                visit[j][k] = True
                bfs(j, k, i)
                count += 1
    arr.append(count)
print(max(arr))