[백준] DFS, BFS (단지번호붙이기)

#2667 단지번호붙이기

 

DFS 사용:

 

1차시도 (틀렸습니다)

n=int(input())
graph=[]
for _ in range(n):
    graph.append(list(map(int,input())))

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

global count
count=0
def dfs(x,y):
    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
        if graph[nx][ny]==0:
            continue
        if graph[nx][ny]==1:
            global count
            count+=1
            graph[nx][ny]=0
            dfs(nx,ny)
    
blocks=[]
for i in range(n):
    for j in range(n):
        if graph[i][j]==1:
            dfs(i,j)
            blocks.append(count)
            count=0

print(len(blocks))
blocks.sort()
for i in blocks:
    print(i)

 

로 했는데 분명 주어진 테스트케이스를 실행하면 출력 예시랑 똑같이 출력은 되는데

왜인지 오답처리되었다....

그래서 다른 사람들 답과 비교해보니 dfs함수에서 return True/ False를 안해줘서 그런가 하고 수정해보았다.

 

2차시도 (틀렸습니다):

n=int(input())
graph=[]
for _ in range(n):
  graph.append(list(map(int,input())))

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


count=0
def dfs(x,y):
  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:
      return False
      continue
    if graph[nx][ny]==0:
      return False
      continue
    if graph[nx][ny]==1:
      global count
      count+=1
      graph[nx][ny]=0
      dfs(nx,ny)
      return True
    return False
    
blocks=[]
for i in range(n):
  for j in range(n):
    if dfs(i,j)==True:
      blocks.append(count)
      count=0

print(len(blocks))
blocks.sort()
for i in blocks:
  print(i)

아놔 !!!! 왜 계속 틀렸다는거야 !!!!!

> 문제는 함수 호출할 때 (x,y)를 인자로 호출하였다면 위의 함수는 (x,y)를 기준이 아닌 그의 인접한 좌표 (nx,ny)를 기준으로 1인지 아닌지를 판단한다는 점이다. 그렇게 되면 밑에서 이중반복문을 돌리면서 모든 블럭에 대해 True/False 판단시 첫번째 시작점은 dfs함수를 거치지 못하게 된다. 누락되는 것이다.

 

따라서 아래와 같이 dfs(x,y)면 (x,y)부터 바로 판단이 가능하도록 고쳤다. 

 

3차시도 (맞았습니다!!):

n=int(input())
graph=[]

for _ in range(n):
  graph.append(list(map(int,input())))

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

def dfs(x,y):
    if x<0 or y<0 or x>=n or y>=n:
      return False
    if graph[x][y]==0:
      return False
    if graph[x][y]==1:
      global count
      count+=1
      graph[x][y]=0
      for i in range(4):
        dfs(x+dx[i],y+dy[i])
      return True
    return False
    
blocks=[]
for i in range(n):
  for j in range(n):
    if dfs(i,j)==True:
      blocks.append(count)
      count=0

print(len(blocks))
blocks.sort()
for i in blocks:
  print(i)

.

.

.

.

.

.

이것도 3시간 걸렸다.......

 

 

* 함수 안에서 쓰인 변수를 밖에서 불러올거면 global 선언하는 거 잊지 말기. 함수 안에서 전역변수를 사용하려면 변수 앞에 global 선언해주고 사용해야 함수 밖에서도 바뀐 값이 유지된다.

위에서처럼 함수 바깥에서 처음 변수 선언해줄 때부터 global 선언해도 되지만,

(함수 안으로 들어온 다음에 밖에 있던 변수를 global 로 선언해줘도 무관)