백준 1012 문제풀이 [python]

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

문제를 보자.

이번 문제도 그래프 탐색 문제이다.

 

필자는 bfs방식을 채택하였다.

 

코드를 보자

 

코드

from collections import deque

a = int(input())

queue = deque()

count = 0

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

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

for i in range(a):

    array = []

    n, m, c = map(int,input().split())

    for j in range(c):

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

    queue.append((array[0]))

    while queue:

        k = queue.popleft()

        array.remove(list(k))

        for i in range(4):

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

            if list((x,y)) in array:

                queue.append((x,y))

                break

        else:

            count += 1

            if len(array) > 0:

                queue.append(array[0])

            else:

                print(count)

                count = 0

일단 틀린 코드이다.

 

나는 논리상 오류가 없다고 생각하지만, 있다.

 

오늘은 너무 피곤해 내일 다시 오겠다.

________________________________________________________________________

마음속에 짐이 있으면, 편하게 잘 수 없다.

 

문제를 조~금의 참고 후 풀어냈다.

 

코드

from collections import deque

a = int(input())

queue = deque()

count = 0

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

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

def bfs(w):

    array.remove(w)

    queue.append(w)

    while queue:

        k = queue.popleft()

        for i in range(4):

            nx, ny = k[0]+dx[i], k[1]+dy[i]

            if list((nx,ny)) in array:

                array.remove(list((nx,ny)))

                queue.append((nx,ny))

           

for i in range(a):

    array = []

    n, m, c = map(int,input().split())

    for j in range(c):

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

    array.sort()

    count = 0

    while array:

        bfs(array[0])

        count += 1

    print(count)

짜증 난다.

 

이제 dfs, bfs 좀 혼자 풀어내자 진짜;

 

일단 백준에서 가장 많이 풀린 문제 TOP 100을 다 풀고 나서 개별 부분에 집중해야겠다.

 

대충 보니 15문제 좀 안 남은 거 같은데, 분발하자.

 

배운 점

1. 그래프 문제풀 때, 함수로 만들어서 쓰자, 괜히 한 번에 끝내려 하지 말고