[백준-파이썬] 2468: 안전 영역

백준 2468번 문제!

🔑코드와 설명

BFS로 풀었다.

from collections import deque
import copy

#위, 아래, 오른쪽, 왼쪽을 체크하기 위해서
dx=[-1,0,1,0]
dy=[0,1,0,-1]

#입력 받기
n=int(input())
zone=[list(map(int,input().split())) for _ in range(n)]

#가장 낮은 곳, 가장 높은 곳을 파악하려고 함
start=float('inf') #가장 낮은 곳의 높이 (사실 이 값은 사용하지 않음..)
finish=-float('inf') #가장 높은 곳의 높이
for i in zone:
    for j in i:
        if j <start:
            start=j
        elif j>finish:
            finish=j

safe_zone=[] #여기에 강수량 별로 안전 영역 갯수를 넣을 것
for rain in range(finish): #아무 지역도 물에 잠기지 않을 수도 있어서 0부터, 가장 높은 곳 높이까지 살펴볼 것

    Q=deque()
    cnt=0 #강수량 별로 안전 영역 갯수 카운트
    zone_tmp=copy.deepcopy(zone) #매번 zone을 복사해서 zone_tmp를 만듦

    for w in range(n):
        for z in range(n):
            if zone_tmp[w][z]>rain: #쭉~ 보면서 만약에 비온 양보다 높은 지역에 있다면
                cnt+=1 #안전 영역 하나 추가!
                zone_tmp[w][z]=0 #거기 높이를 0으로 바꿈(다시 세지 않도록)
                Q.append((w,z)) #Q에 그 위치값 넣음

                while Q: #Q 안에 값이 있다면
                    tmp=Q.popleft() #아까 넣은 위치값을 빼서 튜플 형태로 만듦
                    for r in range(4): #상하좌우를 살펴봄
                        xx=tmp[0]+dx[r]
                        yy=tmp[1]+dy[r]
                        if 0<=xx<n and 0<=yy<n and zone_tmp[xx][yy]>rain: #만약 해당 위치값 기준으로 상하좌우 중에서 안전 영역 있다면
                            zone_tmp[xx][yy]=0 #거기 높이를 0으로 바꿈(다시 세지 않도록)
                            Q.append((xx,yy)) #또 그 위치를 기준으로 상하좌우 살펴보려고 Q에 넣음
    safe_zone.append(cnt) #다 살펴봤으면 안전 영역 갯수를 safe_zone 리스트에 넣음

print(max(safe_zone)) #안전 영역 최대 갯수가 정답!

✨배운 것

깊은 복사!!

깊은 복사와 얕은 복사가 있다는 것을 알았다.
처음에는 zone_tmp=copy.deepcopy(zone)부분을 zone_tmp=copy.copy(zone)으로 했었다. 그랬더니 답이 이상했다..! zone을 살펴보니, 두번째 복사될 때부터 전체 0으로 복사가 되었다. 이것은 얕은 복사이기 때문이었다.
zone_tmp=copy.deepcopy(zone)로 하니까 잘 풀렸다!!
파이썬 기본을 갈고 닦자-얕은 복사와 깊은 복사 이걸 꼼꼼히 읽어봐야겠다!!
이 분의 포스팅도 읽으니 이해가 되었다.
내가 이해한 것을 써보겠다.

리스트는 mutable 객체이다. 그래서 그 값을 바꿔도 계속 같은 객체를 가리킨다.

그 원소가 immutable객체인 경우에는 얕은 복사나 깊은 복사가 차이가 없다. 그렇지만 그 원소가 mutable 객체인 경우에는 차이가 있다.

위의 코드에서 zone은 2차원 리스트이다. 그러니까 리스트의 원소가 mutable 객체인 것이다. 이럴 때 깊은 복사와 얕은 복사일 때 어떤 차이가 있을까?

얕은 복사를 하면, 복사한 리스트(zone_tmp)의 원소가 복사당한(?) 리스트(zone)의 원소를 참조한다. 그래서 zone_tmp=copy.copy(zone)로 했을 때는, 한번만 zone_tmp가 의도대로 복사되었고 그 이후에는 다 0으로 복사된 것이다. 아래 이미지 캡처는 zone를 zone_tmp에 얕은 복사한 직후에 zone_tmp를 출력한 것이다. 코드로 하면 아래와 같다.

zone_tmp=copy.copy(zone)
for zo in zone_tmp:
        print(zo)
print()

zone_tmp 원소가 zone의 원소인 리스트들을 참조해서, zone_tmp의 리스트의 값을 바꿀 때, zone의 리스트의 값이 바뀐 것이다.

반면에 깊은 복사를 하면 복사한 리스트(zone_tmp)의 원소가 복사당한 리스트(zone)의 원소와는 상관없이 새로운 객체가 된다. 그래서zone_tmp=copy.deepcopy(zone)으로 했을 때는 의도대로 복사된 것이다. 아래 이미지 캡처는 zone를 zone_tmp에 깊은 복사한 직후에 zone_tmp를 출력한 것이다. 코드는 위와 같다.

zone_tmp의 원소인 리스트의 값들이 바뀔 때, zone과는 상관없이 독립적인 객체라서, 당연히 zone은 변함없었던 것이다.

😊 읽어주신 분들께..
읽어주셔서 감사합니다.
이해된 것이 기뻐서 썼는데, 잘 설명했는지는 모르겠네요ㅠㅠ
제게 질문주셔도 좋고, 오류가 있다면 짚어주셔도 좋습니다 ㅎㅎ
제가 참고한 사이트들을 보시면 깊은 복사-얕은 복사, mutable-immutable 이해가 잘 되실 것 같습니다 ㅎㅎ (파이썬 기본을 갈고 닦자-얕은 복사와 깊은 복사, 이 분의 포스팅)