백준 > 단지번호붙이기

❓ 문제

백준 실버 1 문제 > 단지번호붙이기

❗ 해결

bfs/dfs 문제이며, 지도를 2중 for 문으로 반복하면서, 해당 지도 배열의 값이 1인 곳을 찾으면 bfs/dfs를 돌린다.
bfs를 실행하면서 방문한 집은 값을 0으로 바꿔준다.

from collections import deque

def bfs(x, y):
    queue = deque()
    house_count = 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue.append([x, y])

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] == 1:
                queue.append([nx, ny])
                maps[nx][ny] = 0
                house_count+=1

    return house_count

N = int(input())

maps = [list(map(int, input())) for _ in range(N)]

h = len(maps)
w = len(maps[0])

count = 0
result = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            result.append(bfs(i,j))
            count += 1

result.sort()
print(count)
for r in result:
    print(r)

처음엔 이렇게 했는데 자꾸 틀렸습니다가 나왔다.
이런저런 테스트케이스를 도입하던 중

4
0000
0000
0000
0001

입력이 이렇게 주어진 경우, 출력이

1
0

으로 나오는 문제가 발생했다. 곰곰히 생각해보니 bfs로 처음 방문했던 곳을 체크하지 않아서 생기는 문제라고 판단이 되었다.
그래서 처음 방문한 곳을 체크해주는 로직을 추가 했다.
바뀐 부분은 이부분이다.

def bfs(x, y):
    queue = deque()
    house_count = 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue.append([x, y])

    while queue:

여기서 house_count를 0으로 설정해버리면 아까와 같은 테스트케이스에서 그냥 house_count가 0인 채로

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] == 1:
                queue.append([nx, ny])
                maps[nx][ny] = 0
                house_count+=1

해당 로직을 타는데 house_count += 1을 해주지 못하고 그대로 return되기 때문에

1
0

이라는 결과값이 출력이 되었다.

따라서

def bfs(x, y):
    queue = deque()
    house_count = 1

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    maps[x][y] = 0
    queue.append([x, y])

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]


            if 0 <= nx < N and 0 <= ny < N:
                if maps[nx][ny] == 1:

                    queue.append([nx, ny])
                    maps[nx][ny] = 0
                    house_count += 1


    return house_count

위 코드와 같이 house_count를 1로 설정해 주고, 처음 방문한 곳 (bfs를 시작한 지점)을 0으로 만들어주고 순회를 하게 되면 정상적인 결과값이 나오게 된다.

전체 소스

from collections import deque

def bfs(x, y):
    queue = deque()
    house_count = 1

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    maps[x][y] = 0
    queue.append([x, y])

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

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]


            if 0 <= nx < N and 0 <= ny < N:
                if maps[nx][ny] == 1:

                    queue.append([nx, ny])
                    maps[nx][ny] = 0
                    house_count += 1


    return house_count

N = int(input())

maps = [list(map(int, input())) for _ in range(N)]

h = len(maps)
w = len(maps[0])

count = 0
result = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            result.append(bfs(i,j))
            count += 1

result.sort()
print(count)
for r in result:
    print(r)