백준 2667 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

보자마자 이전에 풀었던 문제가 생각남과 동시에 bfs가 떠올랐다.

 

추후 알게 되었지만 dfs로도 풀 수 있다.

 

코드

from collections import deque

queue = deque()

num = 0

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

a = int(input())

array= []

memory = []

result =[]

count =0

for i in range(a):

    array.append(list(map(int,input())))

   

for x in range(a):

    for y in range(a):

        if array[x][y] == 1:

            memory.append((x,y))        

def bfs():

    global count

   

    if len(memory) == 0:

        return

    queue.append(memory.pop(0))

    array[queue[0][0]][queue[0][1]] = 0

    while queue:

        location = queue.popleft()

        for i in range(4):

            x, y = dx[i] + location[0], dy[i] + location[1]

            if (x,y) in memory and array[x][y] == 1:

                count += 1

                queue.append((x,y))

                memory.remove((x,y))

                array[x][y] = 0

    else:

        result.append(count+1)

        count = 0

        bfs()

bfs()

result.sort()

print(len(result))

for i in result:

    print(i)

memory에 단지의 위치정보를 모두 넣은 후, 인접 단지를 모두 0으로 만들고, 방문된 곳은 memory에서 삭제하며 수행한다.

 

비록 오랜 시간이 걸렸지만, 직접 짠 코드다.

 

그래서 더 의미있다.

 

하지만 분명 코드를 줄일 수 있다고 생각하였다.

 

그래서 코드를 gpt에 넣고 간소화시켜달라고 요청해 보았다.

from collections import deque

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

a = int(input())

array = [list(map(int, input())) for _ in range(a)]

memory = []

def bfs(x, y):

    count = 1

    queue = deque([(x, y)])

    array[x][y] = 0

    while queue:

        x, y = queue.popleft()

        for i in range(4):

            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < a and 0 <= ny < a and array[nx][ny] == 1:

                count += 1

                array[nx][ny] = 0

                queue.append((nx, ny))

    return count

result = []

for x in range(a):

    for y in range(a):

        if array[x][y] == 1:

            result.append(bfs(x, y))

result.sort()

print(len(result))

for count in result:

    print(count)

좀 더 직관적으로 바뀌었다.

 

두 번째 코드는, 배열을 모두 돌며 1을 찾을 때마다 덩어리를 탐색한다.

 

또한 탐색이 된 곳은 0으로 하여 타깃이 되지 않도록 한다.

 

처음엔 어떻게 단지의 시작점을 잡을까라고 생각했었다.

 

하지만 gpt가 짜준 코드를 보고 그냥 모두 방문해 보면 되는구나라고 깨달았다.

 

아직은 생각의 확장이 모자라다.

 

생각을 넓혀야겠다.

 

배운 점

1. 앞으론, 배열을 선언할 때, for문을 사용하여 넣도록 해야겠다.