[Baekjoon] 2667_단지번호붙이기

Silver I

문제(출처: https://www.acmicpc.net/problem/2667)

---

<단지 번호 붙이기>

문제 

 

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선 상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

 

입력

 

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그다음 N 줄에는 각각 N개의 자료(0 혹은 1)가 입력된다.

 

출력 

 

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지 내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

 

문제 풀이

- my solution

import sys

def bfs(graph, x,y, visited): #너비 우선 탐색
    dx=[-1,0,0,1] #상,좌,우,하
    dy=[0,-1,1,0]
    check=0 # 단지에 속하는 집의 수

    temp=[[x,y]] # start
    while temp:
        x=temp.pop(0)
        if visited[x[0]][x[1]]==False: #아직 방문하지 않았다면
            visited[x[0]][x[1]] = True # 방문
            check+=1
            for i in range(4):
                a=x[0]+dx[i]
                b=x[1]+dy[i]
                if a>=0 and a<len(graph) and b>=0 and b<len(graph): #범위에 속하면
                    if graph[a][b]==1 and visited[a][b]==False: # 집이 있고, 아직 방문하지 않았다면
                        temp.append([a,b])
    return check

if __name__=='__main__':
    num=int(input())

    arr=[]
    for i in range(num):
        x=list(map(int, sys.stdin.readline().strip()))
        arr.append(x)

    visited=[[False]*num for i in range(num)] #방문 표시 배열
    result=[]
    cnt=0
    for i in range(num):
        for j in range(num):
            if arr[i][j]==1 and visited[i][j]==False: # 집이 있고, 아직 방문하지 않았다면
                temp=bfs(arr, i,j, visited)
                result.append(temp)
                cnt+=1 # 단지 수
    result.sort() # 단지내 집의 수를 오름차순으로 정렬
    print(cnt)
    for i in result:
        print(i)

 

이 문제를 처음 보고 막막했던 부분은 시작 위치를 정하는 부분이었다. 그러다가 단순 반복문을 통해 집이 있고, 아직 방문하지 않은 경우 bfs를 호출하면 된다는 것을 알고는 코드를 구현하기 시작했다. 

 

• bfs(list, 시작 위치 x, 시작 위치 y, 방문 여부 list)
  - 연결된 부분을 찾아야 하기 때문에 상하좌우를 보기 위해 dx, dy 선언
  - check를 통해 단지에 속하는 집의 수 세기, temp list에 시작 위치 x, y 좌표 넣어서 선언
  - temp list가 빌 때까지 반복: temp에서 맨 앞 값을 뽑아와 아직 방문한 집이 아니라면 visited에 표시 후 check+1, 상하좌우 확인하여 list 범위에 속하고, 집이 있으며, 아직 방문하지 않았다면 temp list에 x, y 좌표 추가
  - 단지에 속하는 집의 수 반환
• main
  - 지도의 크기 입력
  - arr, visited, result, cnt 선언
  - arr을 순회하며 집이 있고 아직 방문하지 않은 곳을 찾아 bfs 호출 -> 반환 값을 result에 추가 및 단지 수 cnt +1
  - 단지 내 집의 수를 오름차순으로 정렬 후 출력

내가 이 문제를 풀며 놓쳤던 부분은 2가지였다.

1. 단지 내 집의 수를 오름차순으로 정렬하지 않은 것

2. main문에서 visited 배열을 선언 시 얕은 복사가 이루어져 값이 같이 바뀌는 것

 

1번은 코드를 제출 후 틀렸습니다는 보고 해결할 수 있었다. 문제를 더 꼼꼼히 읽어야겠다...^_^

2번은 검색을 통해 해결할 수 있었다. 코드를 구현 후 원하는 답이 나오지 않아 디버깅을 돌려본 결과 리스트의 값이 한 번에 같이 이루어지는 것을 볼 수 있었다. 그 이유는 처음에 아래와 같이 선언했기 때문이고 이것을 검색해보니 얕은 복사가 이루어졌기 때문이라고 하였다.

 

visited=[[False]*num]*num

 

위와 같은 코드를 

 

visited=[[False]*num for i in range(num)]

 

이와 같이 바꾸었더니 해결할 수 있었다.

---

생각🤔

 

어제 dfs, bfs 개념 문제를 해결한 이후로 dfs, bfs 뿌시기를 하는 중이다. 뿌셔! 👊

근데... 맞게 풀고 있는건가?

---