[boj안전영역] [True]*5와 [True for _ in range(5)]의 차이

백준 안전영역

보기와 다른 동일 개체

프로그래밍을 하다 보면 겉보기엔 여러 개로 보이지만 실제론 동일한 메모리 상의 데이터를 가리키고 있음을 느낄 때가 있다. A = B로 할당을 했을 때 A를 바꿔주면 B도 바뀌는 것이다.
이 문제에서 DFS visited map을 사용할 때, 이런 상황이 있어서 문제가 도무지 풀리지 않았다. 문제 자체는 어렵지 않지만 기초 지식과 경험이 부족했기 때문이다.

# 1
[[False]*5]*5
# 2
[[False for i in range(5)] for j in range(5)]

1과 2가 같은 점은? 5*5의 2차원 리스트가 생성된다는 점이다. 평면상 위치를 표현할 때 사용하기 좋다. 다른 점은? 1은 동일한 개체([False False False False False])가 5개 나열된 것이고 2는 각각 다른 list들이 5개 포함됐다는 점이다. 다시 말해, 평면을 나타내고 i, j에 따른 변화를 표기하려고 할 때는 1번처럼 하면 안된다.

아래를 보면 1은 하나만 바꿨는데 모든 list의 [2]가 True로 바뀌었고, 2는 [0][2]만 바뀌었다. 탐색에서 visited map이 이처럼 잘못 업데이트되면 답을 구할 수 없음 뿐더러 버그 포인트를 찾아내기가 굉장히 어렵더라.

Question

높이가 주어지고 비가 왔을 때 잠기지 않은 영역의 수를 찾는 문제이다. 섬의 개수, 얼음의 개수 등과 유사하다. BFS나 DFS로 풀 수 있다.
다만 강수량을 주지 않았기 때문에 가능한 강수량들을 가정하고 모두 체크한 후 최대값을 찾아야 한다.

Solution

• 확인해야할 max, min 강수 높이를 뽑는다. max(max(list))
• visited map을 만든다. (같은 사이즈)
• DFS를 구성한다. 갈 수 있는 지점(dx, dy)이 지도 전체를 벗어나지 않도록 한다.
• for height range(min+1, max)
  temp = 0
  전체 i, j에 대해 DFS를 돌린다. 한 번의 탐색이 끝나면 temp += 1
  하나의 height에 대해 탐색이 끝나면 max(ans, temp)로 업데이트

아래 visited를 [False]*5 형태로 구성을 해뒀더니 하나를 수정했을 때 모든 라인이 똑같이 바뀌어 visited_map이 정상적으로 작동하지 않았다. 그래서 계속 답이 나오지 않았고.. 하나하나 print를 찍어본 결과 visited 업데이트가 잘못되고 있는 것을 발견할 수 있었다.

def sol(map_, length):
    #visited = [[False]*length]*length # 이 부분!!
    visited = [[False for i in range(length)] for j in range(length)]
    max_height = max(max(map_))

    def check_loc(loc, standard, visited):
        nonlocal map_, length
        i,j = loc[0], loc[1]
        if i < 0 or i >= length: return False
        if j < 0 or j >= length: return False
        if map_[i][j] <= standard: return False
        if visited[i][j]: return False
        return loc
    
    def dfs_helper(root, standard):
        i, j = root[0], root[1]
        visited[i][j] = True
        #print('aaa', visited)
        togo = [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]
        #print('root:', root)
        
        togo1 = [check_loc(loc, standard, visited) for loc in togo]
        #print('togo:', togo1)
        for loc in togo1:
            if loc: dfs_helper(loc, standard)
    
    ans = 0
    for height in range(max_height):
        temp = 0
        for i in range(length):
            for j in range(length):
                if not visited[i][j] and map_[i][j] > height:
                    dfs_helper((i,j), height)
                    temp += 1
        ans = max(ans, temp)
        visited = [[False for i in range(length)] for j in range(length)]
    
    return ans

github