[BAEKJOON] 2667. 단지번호 붙이기

 

---

[백준 2667번: 단지번호 붙이기]
👉 https://www.acmicpc.net/problem/2667

 

이번에도 DFS 문제. BFS는 DFS에 비해 살짝은 낯설어서 DFS로 풀었다. 근데 풀기가 어려웠어...

N = int(input())    # 지도 크기

arr = [list(map(int, input().strip())) for _ in range(N)]

answer = []

visited = [[False] * N for _ in range(N)]

def dfs(x, y):

    visited[x][y] = True

    count = 1

    for dx, dy in [(0,1), (1,0), (-1,0), (0,-1)]:

        nx, ny = x+dx, y+dy

        if 0 <= nx < N and 0 <= ny < N:

            if not visited[nx][ny] and arr[nx][ny] == 1:

                count += dfs(nx, ny)

    return count

for i in range(N):

    for j in range(N):

        if arr[i][j] == 1 and not visited[i][j]:

            result = dfs(i, j)

            answer.append(result)

answer = sorted(answer)

print(len(answer))

for cnt in answer:

    print(cnt)

구현 로직을 작성한 노트. 나중에 다시 풀어봐야 할 듯 하다.

 

[구현 시도 중 놓친 부분들]

• arr 내에서 1인 값의 인덱스만 고려하려고 one_value를 만들었었다. 근데 막상 만들어놓고 보니까 dfs 내에서 사용을 하니 복잡해져서 방향을 틀었다. arr 내에서 방문하지 않고 + 1 값을 가진 인덱스를 대상으로 하는 건 맞지만, 그 상태에서 바로 dfs 함수를 적용시켜줬다. 그러면 단지 내 집의 수를 구할 수 있으므로.
• dfs 함수를 구현하다가 count가 필요하다는 걸 깨달았다. 노트를 보면 처음에 아예 작성조차 안되어 있음을 볼 수 있는... dfs 함수 외부에 선언했다가 단지 바뀔 때마다 초기화가 너무 귀찮아서 그냥 함수 내부에서 처음부터 1로 시작하게 만들어줬다.

 

이번 문제는 뭔가... 어렵긴 했는데, 제대로 정신만 차리면 풀 수 있을 것 같기도 한... 저렇게 단지 내 아파트 수랑 단지 총 수를 구하는, 저런 2차원 격자에서 연결된 컴포넌트를 세는 유의 문제는 몇 번 접해도 쉬워지지 않는 것 같다. 저런 비슷한 문제 뭘 풀었더라?

...뭘 풀었나 했더니, 최근에 삼성 코테 보러 가서 접한 문제였던 것 같다. 쩝...