[ 파이썬(python) ] 백준 2667 - 단지번호붙이기

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

문제 설명

---

💡 나의 풀이

아침부터 저녁까지 이 문제만 잡고 늘어졌는데 드디어 풀었다. 😇 😇 특히, 처음에 방문한 좌표를 1로 선언한 이유와, 새로운 좌표를 1로 선언한 이유를 잘 몰라서 엄청 헤맸다.

 

이 문제는 BFS, DFS 파트에 약한 나에게 많은 도움을 준 문제다. 또, BFS와 DFS로 풀 수 있는데 지금은 BFS버전이고 내일은 DFS로 풀어봐야겠다.

 

푸는 방법으로 append와 flag방식 두 개로 나눠서 풀었는데 flag 실행시간이 append 보다 4ms정도 더 빨랐다.( 4ms면 별 의미 없는 시간차이긴 하지만, True, False가 근소하게 더 빠르다는 것을 참고적으로 알아두자!)

 

 

개별 단지수를 구하는 코드는 고민을 많이 했는데, 결론적으로 {}를 이용해서 풀었다.

이 문제에서 구현해야 하는 기능은 총 2가지로 나뉘는데 다음과 같다.

1. 총 단지수(bfs함수를 실행하는 조건이 충족된 횟수, 3번)
2. 개별 단지수(bfs함수를 실행하는 횟수, 7, 8, 9)

 

풀이 방법은 다음과 같다.

1. N * N의 좌표를 모두 확인해야 하므로 이중 반복문을 사용한다.
2. 그렇다고, 모든 좌표를 함수에 대입하는 것이 아닌 조건에 맞는 좌표를 확인하자.(현재 값이 1이고, 아직 방문하지 않은 노드 일 때)
3. 필터링된 값을 bfs함수로 집어넣는다.
4. deque()안에 초기 x, y좌표를 집어넣는다.(이때, 괄호를 하나 더 추가해서 튜플 형태로 넣자.)
5. 초기 좌표는 방문했으므로 1로 바꾼다.
6. queue의 값이 없어질 때까지 popleft()를 하는데 현재 좌표 기준으로 상, 하, 좌, 우의 좌표를 확인하고 1이 발견되면 해당 좌표를 큐에 집어넣는다.
7. 새로운 좌표를 방문했으므로 1로 선언하자.

728x90

조금 더 자세한 풀이 방법을 직접 작성했는데 잘 모르겠으면 다음 사진을 보자 (그림과 글씨 상태는 너그러운 마음으로 이해해주기 바란다.)

 

 

 

# number 확인

from collections import deque

def bfs(x, y, cnt):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = 1

    while queue:
        x, y = queue.popleft()

        for i in range(4):  # Search Up, Down, Left, Right
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N:  # private out of bound
                if graph[nx][ny] == 1 and visited[nx][ny] == 0:  # check current value is house and not visited house
                    queue.append((nx, ny))
                    visited[nx][ny] = 1
                    cnt_dict[cnt] += 1

dx = [-1, 1, 0, 0]  # init Up and Down
dy = [0, 0, -1, 1]  # init Left and Right

N = int(input())  # map_size
graph = [list(map(int, input())) for _ in range(N)]  # input init
visited = [[0] * N for _ in range(N)]  # visited init
cnt = 0  # count all complex number
cnt_dict = {}  # count each complex number

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and visited[i][j] == 0:
            cnt+=1
            cnt_dict[cnt] = 1
            bfs(i, j, cnt)
print(cnt)
print(visited)
print('\n'.join(map(str, sorted(cnt_dict.values()))))

# True, False 방법

from collections import deque

def bfs(x, y, cnt):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True

    while queue:
        x, y = queue.popleft()

        for i in range(4):  # Search Up, Down, Left, Right
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N:  # private out of bound
                if graph[nx][ny] == 1 and visited[nx][ny] == False:  # check current value is house and not visited house
                    queue.append((nx, ny))
                    visited[nx][ny] = True
                    cnt_dict[cnt] += 1

dx = [-1, 1, 0, 0]  # init Up and Down
dy = [0, 0, -1, 1]  # init Left and Right

N = int(input())  # map_size
graph = [list(map(int, input())) for _ in range(N)]  # input init
visited = [[False] * N for _ in range(N)]  # visited init
cnt = 0  # count all complex number
cnt_dict = {}  # count each complex number

for i in range(N):
    for j in range(N):
        if graph[i][j] == 1 and visited[i][j] == False:
            cnt+=1
            cnt_dict[cnt] = 1
            bfs(i, j, cnt)
print(cnt)
print('\n'.join(map(str, sorted(cnt_dict.values()))))