[백준(python)] 2468 안전영역

📌 난이도, 유형

난이도 : 실버 1
유형 : 그래프 이론, 브루트포스, 그래프 탐색, DFS, BFS
시간제한 : 1초
메모리제한 : 128MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

처음 짠 코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
graph = []
q = []

for i in range(N):
    graph.append(list(map(int, input().split())))
maxNum = max(map(max, graph))

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


def bfs(x, y, graph2):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            if graph2[nx][ny] != 0:
                graph2[nx][ny] = 0
                queue.append((nx, ny))
    return 1


for k in range(0, maxNum + 1):
    result = 0
    for p in graph:
        graph2 = [[0 if element <= k else element for element in row] for row in graph]
    for i in range(N):
        for j in range(N):
            if graph2[i][j] != 0 and graph2[i][j] > k:
                result += bfs(i, j, graph2)
    q.append(result)
print(max(q))

바꾼 코드

import sys
from collections import deque

input = sys.stdin.readline


# 3. bfs함수 구현
def bfs(x, y, high):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue
            if graph[nx][ny] > high and visited[nx][ny] == 0:
                visited[nx][ny] = 1
                queue.append((nx, ny))


# 1. 입력값 받기
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
# 최대 높이값 구하기
high = max(map(max, graph))
# 방향
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

MAX = 0
# 2. 수심에 따라 달라지는 안전영역 갯수 비교
for t in range(high):
    visited = [[0] * n for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if graph[i][j] > t and visited[i][j] == 0:
                visited[i][j] = 1  # 방문표시
                bfs(i, j, t)
                cnt += 1
    if MAX < cnt:
        MAX = cnt
print(MAX)

---

📝 해설

처음에는 visited를 사용하지 않고 짜려고 해서 엄청 오래걸렸다..

입력받은 graph에서 일정 수심 이하의 값을 모두 0으로 만든 graph2를 새로 만들어서 거기서 bfs를 돌리려고 했는데 코드가 너무 더러워지고 시간도 오래 걸려서 다시 짰다.

어쩄든 이 문제를 풀 때 제일 중요한 점은

1. 아무지역도 물에 잠기지 않을 수가 있다.

• 문제 예제입력 아래 메모에 적혀있다. 자칫 그냥 넘어갈 수 있는데 이를 고려하지 않고 코드를 짜면 80%쯤에서 틀렸습니다가 나온다.

  반례 
  2
  1 1
  1 1
  answer : 1

  해결 방법으로는 수심에 따른 반복문이 1부터 아닌 0부터 시작하면 된다.

2. max 값 구하기

• 최대수심값을 구할 때

  high = max(max(graph))

  이걸로 하면 틀린다.
  왜냐하면 저 값은 "첫 원소가 가장 큰 리스트"에 속한 값을 반환하기 때문이다.

a  = [[1, 999],
     [3, 4],
     [2, 4, 6]]
print(max(a))
print(max(max(a)))    
output:
[3, 4]
4

해결방법

high = max(map(max, graph))

map(max, graph)로 각 행의 최대값을 추출하고, 그 중에서 전체 리스트의 최대값을 max(...)를 통해 찾아 graph의 최대값을 구하면 된다.