정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 연결된 집들끼리 단지를 구성하고 단지별로 각각의 집 개수를 구하여라.
DFS, BFS 개념은 다 이해했는데 문제풀이에 적용하는 것에는 아직 익숙하지 않다.
결론적으로 1이 연결된 부분을 찾는 거니까 DFS를 이용하면 될거라 판단했다.
논리상으론 맞지만 코드가 어긋났는지 무한루프가 돌게 되었다.
import sys
input = sys.stdin.readline
N = int(input())
graph = []
for _ in range(N):
graph.append(list(map(int, input().strip())))
visited = [[0]*N]*N
def dfs(x, y):
count = 0
x, y = 0, 0
moves = [(0, -1), (0, 1), (-1, 0), (1, 0)]
dx, dy = x, y
while True:
for i in range(4):
dx = x + moves[i][0]
dy = y + moves[i][1]
if dx < 0 or dy < 0 or dx >= N or dy >= N: # 길 아님
continue
if graph[dy][dx] == 1 and visited[dy][dx] == 0: # 집인데 안가봄
visited[dy][dx] = 1
count += 1
x, y = dx, dy
break
elif graph[dy][dx] == 0 and visited[dy][dx] == 0: # 집 없는데 안가봄
graph[dy][dx] = 1
visited[dy][dx] = 1
x, y = dx, dy
break
if visited[x][y] == 0:
break
return count
answer = []
for i in range(N):
for j in range(N):
answer.append(dfs(i,j))
print(len(answer))
answer.sort()
for i in answer:
print(i)
내가 생각한 논리와 일치하는 코드다.
내가 dfs 함수를 만든 이유는 하나의 단지를 찾은 이후 또다른 단지를 찾을 때 조건식이 애매하였기 때문이다.
근데 이것저것 하다보니 만든 이유를 잊어버리고 재귀를 이용하지 않았다. 함수를 만들고 while문을 써버렸다...ㅋㅋㅋㅋㅋㅋㅋㅋ
자신의 위치를 움직여서 위치를 파악하는 문제유형이 많다. 이동한 위치를 인자로 넣어 재귀함수를 만들면 해당 위치에 대한 정보 파악이 가능하므로 기억해두어야 한다.
import sys
input = sys.stdin.readline
N = int(input())
graph = []
for _ in range(N):
graph.append(list(map(int, input().strip())))
visited = [[0] * N] * N
count = 0
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
global count
if x < 0 or y < 0 or x >= N or y >= N:
return False
if graph[x][y] == 1:
count += 1
graph[x][y] = 0
for i in range(4):
dfs(x + dx[i], y + dy[i])
return True
answer = []
for i in range(N):
for j in range(N):
if dfs(i, j) == True:
answer.append(count)
count = 0
print(len(answer))
answer.sort()
for i in answer:
print(i)