[백준] 2468번: 안전 영역 - python

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

무지성으로 가장 큰 값을 기준으로 for문을 돌리면서 한번씩 한번씩 BFS를 진행한다. 그리고 할때마다 값을 answer리스트에 추가해주고 최종으로 answer에서 가장 큰 값을 뽑아낸다.

 

처음 작성한 코드. 그러나 69퍼에서 바로 런타임에러 발생..

생각보다 BFS에서 상당히 자주 일어나는 것 같다.

이럴때 런타임에러가 발생하는 이유는 모든 영역이 1일때 for문이 제대로 작동을 안하기 때문이었다. 

from collections import deque
n = int(input())

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

answer = []
dq = deque()
maxhigh = max(max(arr)) #최고높이
for _ in range(1, maxhigh):
    ch =[[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            if arr[i][j] <= _:
                ch[i][j] = 1

    cnt = 0
    for i in range(n):
        for j in range(n):
            if ch[i][j] == 0:
                cnt += 1
                dq.append((i, j))

                while dq:
                    x, y = dq.popleft()
                    
                    for k in range(4):
                        nx = dx[k] + x
                        ny = dy[k] + y

                        if 0<=nx<n and 0<=ny<n:
                            if ch[nx][ny] == 0:
                                ch[nx][ny] = 1
                                dq.append((nx, ny))
    answer.append(cnt)

print(max(answer))

 

수정해서 

 

from collections import deque
n = int(input())

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

answer = []
dq = deque()
maxhigh = max(max(arr)) #최고높이
for _ in range(maxhigh, -1, -1):
    ch =[[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            if arr[i][j] <= _:
                ch[i][j] = 1

    cnt = 0
    for i in range(n):
        for j in range(n):
            if ch[i][j] == 0:
                cnt += 1
                dq.append((i, j))

                while dq:
                    x, y = dq.popleft()
                    
                    for k in range(4):
                        nx = dx[k] + x
                        ny = dy[k] + y

                        if 0<=nx<n and 0<=ny<n:
                            if ch[nx][ny] == 0:
                                ch[nx][ny] = 1
                                dq.append((nx, ny))
    answer.append(cnt)

print(max(answer))

 

인데도 86%에서 계속해서 틀렸다고 발생하였다. 생각해봤는데 도저히 모르겠어서 질문게시판을 보니 max(max(arr))문제가 있다고 말씀해주셨다. 

 

찾아보니 다음과 같은 예시를 볼 수 있었다..

data = [[1, 2, 3], [5], [0, 1, 100]]
print(min(data))	# [0, 1, 100]
print(max(data))	# [5]

 

결론은 2차원배열에서의 비교는 첫번째 원소만 비교해서 가장 작거나 큰 값을 도출해낸다는 것이었다.

무지성 max max는 금하자..

 

다음은 지금까지의 에러사항을 고친 최종 수정 코드다. 

 

from collections import deque
n = int(input())

dx = [0, 1, -1, 0]
dy = [1, 0, 0, -1]
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))

answer = []
dq = deque()
maxhigh = max(map(max, arr)) #최고높이
for _ in range(maxhigh, -1, -1):
    ch =[[0 for i in range(n)] for j in range(n)]

    for i in range(n):
        for j in range(n):
            if arr[i][j] <= _:
                ch[i][j] = 1

    cnt = 0
    for i in range(n):
        for j in range(n):
            if ch[i][j] == 0:
                cnt += 1
                dq.append((i, j))

                while dq:
                    x, y = dq.popleft()
                    
                    for k in range(4):
                        nx = dx[k] + x
                        ny = dy[k] + y

                        if 0<=nx<n and 0<=ny<n:
                            if ch[nx][ny] == 0:
                                ch[nx][ny] = 1
                                dq.append((nx, ny))
    answer.append(cnt)

if max(answer) != 0:
    print(max(answer))
else:
    print(1)

 

완성