* 백준 2667번 - 단지번호붙이기

Gyuhan Park·2022년 1월 4일
0

코딩테스트 정복

목록 보기
41/47

정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 연결된 집들끼리 단지를 구성하고 단지별로 각각의 집 개수를 구하여라.

# 틀린 코드

DFS, BFS 개념은 다 이해했는데 문제풀이에 적용하는 것에는 아직 익숙하지 않다.
결론적으로 1이 연결된 부분을 찾는 거니까 DFS를 이용하면 될거라 판단했다.

  1. 상하좌우를 이동해 방문하지 않은 1을 찾고 카운팅을 한다.
  2. 네 방향을 다찾아도 1이 없는 경우 새로운 단지를 찾는다.
  3. 집의 위치를 모르기때문에 지도 전체를 순회하기 위해 이중 for문을 작성하였다.

논리상으론 맞지만 코드가 어긋났는지 무한루프가 돌게 되었다.

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)
profile
단단한 프론트엔드 개발자가 되고 싶은

0개의 댓글