[BOJ][DFS] 백준 2667번 파이썬: 단지번호붙이기 --얕은복사와 깊은복사, dfs
#2667 (단지번호붙이기)
다시 풀어봐도 답을 맞힐 자신이 없어서 다시 한 번 풀어봤는데 역시나 오답..
테스트케이스대로 출력도 안되고
아무리 코드를 다시 찬찬히 살펴봐도 어디가 틀린지 모르겠었던..
1차 시도: (-- 오답 --)
#2667 단지번호붙이기
n=int(input())
graph=[]
for _ in range(n):
graph.append(list(map(int,input())))
visited=[[False]*n]*n
count=0
num=[]
a=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def dfs(x,y):
graph[x][y]=a
visited[x][y]=True
global count
count+=1
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx>=n or ny>=n or nx<0 or ny<0:
continue
if graph[nx][ny]==0:
continue
if visited[nx][ny]==False:
dfs(nx,ny)
for i in range(n):
for j in range(n):
if graph[i][j]==1 and not visited[i][j]:
a+=1
dfs(i,j)
num.append(count)
count=0
print(len(num))
for i in num:
print(i)
와
정확히 2시간 지나고서야
찾았다
아무리 봐도 어디가 문젠지 모르겠었는데
문제는
visited 리스트를 *n으로 얕은복사해서 만든게 문제
그냥 이중 for문으로 visited 2차원 배열 만들어주니까
멀쩡히 돌아간다 ㅠㅠㅠ
++) 아 그리고 오름차순 정렬을 안했다. num.sort() 추가해주기
2차시도: (--함수에서 True/False값 반환하도록 바꿔봄--)
#2667 단지번호붙이기
n=int(input())
graph=[]
for _ in range(n):
graph.append(list(map(int,input())))
visited=[]
for i in range(n):
visited.append([])
for j in range(n):
visited[i].append(False)
count=0
num=[]
dx=[-1,1,0,0]
dy=[0,0,-1,1]
def dfs(x,y):
if x>=n or y>=n or x<0 or y<0:
return False
if graph[x][y]==0:
return False
if graph[x][y]==1 and not visited[x][y]:
visited[x][y]=True
global count
count+=1
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
dfs(nx,ny)
return True
return False
for i in range(n):
for j in range(n):
if dfs(i,j): ##
num.append(count)
count=0
num.sort()
print(len(num))
for i in num:
print(i)만세 !!!!!!!!!!
으
이렇게 알고리즘 상으로는 문제 없는데
정작 리스트 만들어주는 과정에서 실수 (정확히는 실수는 아니고 착오) 가 있었거나 문제 조건을 놓친 게 있어서
몇시간 (아니 사실 이 문제 며칠동안 애먹었다 ㅠㅠ)동안 삽질하다가 발견하면
어이없어서 헛웃음이 나오기도 하지만 그래도 알고리즘에는 문제가 없었다는 사실에 나름 기분이 좋다.
얏호 ~!
근데 왜 저렇게 *N 으로 리스트를 만들면 안되는가 하면,
*N으로 복사시 깊은 복사가 아닌 얕은 복사이기 때문.
얕은복사란?
변수가 복사된 것 같지만 사실은 변수가 복사된 것이 아니라 실제로는 연결되어 있는 것.
즉, 같은 곳을 참조하도록 한 것이지, 실제로 그 변수가 그대로 복사된 것은 아니다.
따라서 그 참조가 변경되면, 복사된 변수와 복사한 변수의 값이 모두 변경된다.
visited 배열에서 예를 들어 visited[0][0]값만 바꿔도 나머지 visited[i][j]값도 모두 바뀐다. visited 배열을 만들 때 얕은 복사를 사용했기 때문에 모두 같은 곳을 참조하므로.
>> 그니까 이차원 배열을 만들 때는 *N 보다는 for반복문을 이용해 만들어주자 !
얕은복사/ 깊은복사 참고 링크:
https://blockdmask.tistory.com/576
[python] 파이썬 얕은복사, 깊은복사 (copy, deepcopy, [:], =) 총 정리
안녕하세요. BlockDMask입니다. 오늘은 파이썬 얕은 복사, 깊은 복사에 대해서 정리해보려 합니다. 은근히 헷갈려서 천천히 한번 정리해볼게요. <목차> 1. 파이썬 얕은 복사 2. 파이썬 깊은 복사 3. 그
blockdmask.tistory.com
파이썬 2차원 배열 선언, 이 방법은 피하세요!
2차원 배열을 선언해야 하는 백준 BFS 문제를 풀고 있었다. 한 블로그에서 2차원 배열을 선언하는 여러 방법을 올려놨길래, 그 중 내 마음에 제일 드는 짧은 코드를 골라 썼다. 그런데 아무리 봐도
yechoi.tistory.com
+) 언제까지 dfs bfs..? 이거 완벽하게 하고 싶은 마음에 진도를 못 나가고 있는데,,
진도 나가면서 연습을 병행해야겠다.. 내일은 새로운 알고리즘으로 돌아오기...