[백준] 2468 안전 영역 (실버1) / BFS

문제요약

나의 코드 및 설명

• 내가 작성한 코드. 지역의 높이 정보를 저장한 board의 최대 높이를 구하기 위해 이중 for문을 별도로 하나 더 작성했고, for문을 통해 0~최대높이의 숫자만큼 board의 값을 뺀 것을 임시 리스트인 temp_board에 저장하고 bfs 함수를 호출하여 일일이 카운트하였다. 

from collections import deque

def bfs(sx,sy):
    queue = deque()
    queue.append((sx,sy))
    visited[sy][sx] = 1 #시작 좌표 방문처리
    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
            else:
                #다음 좌표가 방문처리 안되었거나 temp_board가 1이상인 곳(안 잠긴 곳)일 때
                if visited[ny][nx] == 0 and temp_board[ny][nx] >= 1:
                    #방문해서 방문처리 해주고
                    visited[ny][nx] = 1
                    #다음 좌표의 temp_board 값을 0으로 갱신(잠긴 곳으로 표시)
                    #잠긴 곳으로 표시해줌으로써 다음 bfs수행 시 안 잠긴 곳에 대해서 bfs수행할 수 있도록 함 
                    temp_board[ny][nx] = 0
                    #큐에 추가해줌으로써 그 다음 좌표가 잠겼는지 안잠겼는지 계속해서 확인한다 
                    queue.append((nx,ny))

n = int(input())
board = [] #지역의 높이 정보 리스트
for _ in range(n):
    board.append(list(map(int, input().split())))

#지역의 높이 정보 중 최대 높이 찾기
max_height = 0
for i in range(n):
    if max_height < max(board[i]):
        max_height = max(board[i])

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

max_count = 0
#0~(최대높이-1) 잠기는 모든 경우의 수 계산
for height in range(max_height):
    #임시 지역 높이 정보 리스트 초기화
    temp_board = [[0]*n for _ in range(n)]

    #height만큼 잠겼을 때, 높이 정보를 temp_board에 저장
    for i in range(n):
        for j in range(n):
            temp_board[i][j] = board[i][j] - height

    count = 0 #잠기지 않는 안전한 영역 초기화
    for k in range(n):
        for z in range(n):
            if temp_board[k][z] >= 1: #좌표 값이 1 이상인 곳은 아직 안잠긴 곳
                visited = [[0]*n for _ in range(n)] #bfs돌기 전 방문처리 위한 리스트 생성
                bfs(z,k) #bfs를 수행하여 temp_board의 안 잠긴 곳을 잠긴 곳으로 표시
                count+=1 #bfs수행했으니 count+1
    
    #height만큼 잠겼을 때 count값이 최대 값인지 확인 
    if max_count < count:
        max_count = count

print(max_count)

다른 코드 및 설명

• 입력값 입력과 동시에 최대 높이를 구하고, height만큼 잠겼을 때 board 값이 height보다 크다면 빼보지 않아도 어차피 잠기지 않은 곳이므로 board에서 height만큼을 빼서 잠긴 곳을 0으로 표시하지 않았다. bfs 함수에서는 다음 좌표의 board 값이 height 보다 크고, visited == 0 즉, 방문하지 않았다면 큐에 다음 좌표를 넣어주도록 작성했다. 
• 나는 방문한 좌표의 board 값을 bfs함수 내에서 바꿔주었기 때문에 오리지널 board를 사용하지 않고 임시리스트인 temp_board를 그때마다 생성해서 사용했는데, 이 코드에서는 bfs내에서 visited 값만 변경하고, 실제로 bfs를 호출해도 되는 상황인지 visited 리스트로 체크했다.

from collections import deque

def bfs(sx,sy,r):
    queue = deque()
    queue.append((sx,sy))
    visited[sy][sx] = 1 #시작 좌표 방문처리
    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
            else:
                #다음 좌표가 방문처리 안되었거나 board가 height보다 큰 곳(안잠긴 곳. height와 같기만 해도 잠기게 됨)
                if visited[ny][nx] == 0 and board[ny][nx] > height:
                    #방문해서 방문처리 해주고
                    visited[ny][nx] = 1
                    #큐에 추가해줌으로써 그 다음 좌표가 잠겼는지 안잠겼는지 계속해서 확인한다 
                    queue.append((nx,ny))

n = int(input())
board = [] #지역의 높이 정보 리스트
max_height = 0
for _ in range(n):
    board.append(list(map(int, input().split())))
    #현재까지의 최대값과 board에 저장된 마지막 리스트 중 최대값을 비교
    max_height = max(max_height, max(board[-1])) 

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

max_count = 0
#0~(최대높이-1) 잠기는 모든 경우의 수 계산
for height in range(max_height):
    visited = [[0]*n for _ in range(n)]
    count = 0 #잠기지 않는 안전한 영역 초기화
    for k in range(n):
        for z in range(n):
            #board 값이 height보다 크고(안잠기고) 아직 방문처리 안되어 있다면 방문한다.
            if board[k][z] > height and visited[k][z] == 0: 
                bfs(z,k,height) #bfs를 수행하여 board좌표 중 안잠긴 곳을 방문 체크
                count+=1 #bfs수행했으니 count+1
    
    #height만큼 잠겼을 때 count값이 최대 값인지 확인 
    if max_count < count:
        max_count = count

print(max_count)

피드백

내가 접근한 풀이 방식이 틀리진 않았지만, 좀 더 간결하게 클린코드로 문제를 해결할 수 있도록 노력해야겠다. 그동안 DFS, BFS 문제를 풀 때 대부분의 문제가 그리드의 값이 1,0이었는데, 그리드 값을 1,0을 만들지 않아도 BFS 함수 내에서 방문 가능 조건을 달리하여 문제를 해결할 수 있다는 점을 배울 수 있었다.