[TIL 2/2] 백준 2667 단지번호붙이기(graph) python

김경민·2023년 1월 11일
0

TIL

목록 보기
15/15

설계

1번의 하위 항목이 2번의 조건문 아래로 겹치는 것은 구현 할 때,
값이 1이 아니라면 continue로 바꿔서 코드를 조금 더 깔끔하게 바꿨습니다.

  1. 전체를 순회
    • 1의 값이 나온다면, queue 인덱스 삽입, 자신 0으로 치환, dfs시작
  2. dfs
    • 아파트 개수는 1부터 시작
    • 동서남북 조회
      • 조건문 row 좌표, col 좌표 각각 0이상 N미만
      • 1의 값이 나온다면 아파트 개수 +1, 자신 0 치환
      • queue에 현재 인덱스(다음) 삽입
    • 끝난다면 아파트 개수 삽입
  3. 출력

코드

from collections import deque

queue = deque()
N = int(input())
next_rows = [0, 0, 1, -1]
next_cols = [1, -1, 0, -0]
apts = [list(map(int, input())) for _ in range(N)]
results = []


for row in range(N):
    for col in range(N):
        if apts[row][col] != 1:
            continue

        apts[row][col] = 0
        queue.append([row, col])
        count = 1

        while queue:
            r, c = queue.popleft()
            for i in range(4):
                nr, nc = r + next_rows[i], c + next_cols[i]
                if 0 <= nr < N and 0 <= nc < N and apts[nr][nc] == 1:
                    count += 1
                    apts[nr][nc] = 0
                    queue.append([nr, nc])

        results.append(count)

print(len(results))
print('\n'.join(map(str, sorted(results))))
  • 회고
    처음 설계한 그대로 작성해 보기 위해 노력하는데 역시 적다보면 생각하지 못 했던 부분이나 더 좋은 방법이 생각이나는 빈도가 코드를 작성할 때 보다 높은 것 같다.
    코드를 적을 때 설계 부분에서 조금씩 고치지만 큰 틀은 바뀌지 않아 좋았다.
    어제 처음으로 시도해봤던 그래프 문제는 3시간이 걸려도 시간 초과를 해결하지 못했는데,
    두 번째(지금) 문제는 1시간 안 걸렸다^^ 66%이상 줄여버리기~(내일은 아마 30분이면 풀 듯?)
    답을 적고 보면 참 쉬운데 시간이 꽤 걸린게 웃기다 ㅋㅋ
profile
적은 대로 된다.

0개의 댓글