240301 [BOJ/백준] 2468. 안전 영역 (+수정)

 

2468번: 안전 영역 (acmicpc.net)

2468번: 안전 영역

---

나의 코드

1. 비의 양 범위를 N으로 정함(실패)

# 안전 영역
from collections import deque

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

max_v = 0
for i in range(0, N):   # 비의 양이 정해지지 않았기에 0부터 건물 높이까지 1씩 증가하면서 계산
    q = deque()
    visited = [[0] * N for _ in range(N)]
    di = [0, 1, 0, -1]  # 우,하,좌,상 방향 설정
    dj = [1, 0, -1, 0]

    # ans = 0
    count = 0  # 시작 때의 안전영역 수 0부터 시작
    for r in range(N):   # arr 탐색
        for c in range(N):
            # count = 0  # 시작 때의 안전영역 수 0부터 시작
            if arr[r][c] > i and visited[r][c] == 0:  # 비에 잠기지 않고 방문안한 곳부터 시작
                q.append((r,c))
                visited[r][c] = 1 # 시작점 방문표시

                while q: #큐에 값이 있으면 계속 돌아감
                    x, y = q.popleft()

                    for k in range(4):
                        nx = x + di[k]
                        ny = y + dj[k]
                        if 0 <= nx < N and 0 <= ny < N: #이동하려는 곳의 범위가 NxN행렬 안에 있다면
                            if visited[nx][ny] == 1: # 방문한 곳이면 넘어감
                                continue
                            elif arr[nx][ny] > i:  # 방문하지 않고 물에 잠기지 않았다면
                                visited[nx][ny] = 1  # 방문표시
                                q.append((nx, ny))

                count += 1  # 시작점에서 잠기지 않은 연결된 곳 다 탐색했으면 안전영역 수 1 증가
    if max_v < count:
        max_v = count


print(max_v)

2. 비의 양 범위를 건물높이까지 정함(성공)

# 안전 영역
from collections import deque

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

max_v = 0
for i in range(0, 101): # 비의 양이 정해지지 않았기에 0부터 건물 높이까지 1씩 증가하면서 계산
    q = deque()
    visited = [[0] * N for _ in range(N)]
    di = [0, 1, 0, -1]  # 우,하,좌,상 방향 설정
    dj = [1, 0, -1, 0]

    # ans = 0
    count = 0  # 시작 때의 안전영역 수 0부터 시작
    for r in range(N):   # arr 탐색
        for c in range(N):
            # count = 0  # 시작 때의 안전영역 수 0부터 시작
            if arr[r][c] > i and visited[r][c] == 0:  # 비에 잠기지 않고 방문안한 곳부터 시작
                q.append((r, c))
                visited[r][c] = 1  # 시작점 방문표시

                while q: #큐에 값이 있으면 계속 돌아감
                    x, y = q.popleft()

                    for k in range(4):
                        nx = x + di[k]
                        ny = y + dj[k]
                        if 0 <= nx < N and 0 <= ny < N and arr[nx][ny] > i:  #이동하려는 곳의 범위가 NxN행렬 안에 있고 물에 잠기지 않았다면
                            if visited[nx][ny] == 1:  # 방문한 곳이면 넘어감
                                continue
                            visited[nx][ny] = 1  # 방문표시
                            q.append((nx, ny))

                count += 1  # 시작점에서 잠기지 않은 연결된 곳 다 탐색했으면 안전영역 수 1 증가

    if max_v < count:
        max_v = count


print(max_v)

결과

---

처음으로 문제 풀기 전에 어떻게 코드를 짤 지 적어 놓고 시작했다. 아직 답이 나오지 않았고 왜인지는 알지만 해결하지 못하겠다. while문을 돌며 visited에 방문표시를 하는데 그걸 초기화 하는 방법을 모르겠다. 일단 내가 생각한 로직대로 움직이는 것은 확인했으므로 visited 초기화하는 방법만 생각해보든 물어보든 해야겠다. 코드를 완성하고 이 글은 다시 수정하는 걸로 해야겠다.

(+ visited의 초기화는 되고 있었다. 그것까지 확인을 못했을 뿐...ㅎㅎ 그냥 비의 양 범위를 N이 아니라 (0,101)로 했어야했다. 0은 비가 오지 않을 때, 100은 건물의 최대높이이다. 분명 비의 양을 건물 높이로 줄거라고 생각했는데 코드를 짜면서 N을 행과 열의 수가 아니라 건물높이로 착각했다. 코드짜면서 건물의 제일 높은 거 어떻게 설정할거야?라고 생각했었는데 왜 까먹었니...ㅜㅜ 아무튼 그래도 데이터의 초기화 방법을 알 수 있었고 bfs의 구조를 조금은 더 이해할 수 있었던 문제다.)