[백준 1012번] 유기농 배추 (python/파이썬)

Connected component의 갯수를 찾는 문제이다. 프로그래머스에서도 동일한 문제가 있었는데, 프로그래머스에서 통과한 알고리즘대로 풀었는데 계속 시간초과가 떴다. 열심히 찾아보니 알고리즘에서 실수가 있었고 프로그래머스는 테스트 케이스가 적어서 통과한 것 뿐이었다.

 

🌼 문제 링크

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

• 티어: 실버 II
• 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색

 

 

❗ TRIAL 1.

코드

from collections import deque

def check_adj(farm, v, M, N):
    if v[0]<M and v[1]<N:
        if farm[v[0]][v[1]]:
            return True

def bfs(farm, start, M, N):
    queue = deque([start])
    while queue:
        v = queue.popleft()
        farm[v[0]][v[1]] = 0
        adj_right = (v[0], v[1]+1)
        if check_adj(farm, adj_right, M, N):
            queue.append(adj_right)
        adj_bottom = (v[0]+1, v[1])
        if check_adj(farm, adj_bottom, M, N):
            queue.append(adj_bottom)
    return farm

def solution(farm):
    ans = 0
    for m in range(M):
        for n in range(N):
            if farm[m][n]:
                ans += 1
                farm = bfs(farm, (m, n), M, N)

    return ans

T = int(input())

for _ in range(T): #for each test case
    M, N, K = map(int, input().split( ))

    #prepare farm
    farm = [[0 for _ in range(N)] for _ in range(M)]
    for _ in range(K):
        x, y = map(int, input().split( ))
        farm[x][y] = 1

    print(solution(farm))

 

틀린 원인

 

시간초과. 각 node에 대해서 상하좌우 모든 인접한 node를 검사했어야 하는데 오른쪽과 아래만 검사했다.

예외 케이스: https://www.acmicpc.net/board/view/93090

 

 

❗ TRIAL 2.

코드

from collections import deque

def check_adj(farm, v, M, N):
    if v[0]<M and v[1]<N:
        if farm[v[0]][v[1]]:
            return True

def bfs(farm, start, M, N):
    queue = deque([start])
    farm[start[0]][start[1]] = 0
    while queue:
        v = queue.popleft()
        farm[v[0]][v[1]] = 0
        adjs = [(v[0], v[1]+1), (v[0], v[1]-1), (v[0]+1, v[1]), (v[0]-1, v[1])]
        for adj in adjs:
            if check_adj(farm, adj, M, N):
                queue.append(adj)
    return farm

def solution(farm):
    ans = 0
    for m in range(M):
        for n in range(N):
            if farm[m][n]:
                ans += 1
                farm = bfs(farm, (m, n), M, N)

    return ans

T = int(input())

answers = []
for _ in range(T): #for each test case
    M, N, K = map(int, input().split( ))

    #prepare farm
    farm = [[0 for _ in range(N)] for _ in range(M)]
    for _ in range(K):
        x, y = map(int, input().split( ))
        farm[x][y] = 1

    print(solution(farm))

 

수정한 부분

 

- 각 node에 대해 상하좌우 검사하도록 추가

 

틀린 원인

 

시간초과. 상하좌우 node가 유효한 값인지 검사하는 check_adj 함수에서 좌표값이 0보다 큰지 검사하지 않아서 음수 범위의 좌표값을 통과시킴.

예외 케이스: https://www.acmicpc.net/board/view/93090

 

 

❗ TRIAL 3.

코드

from collections import deque

def check_adj(farm, v, M, N):
    if 0<=v[0]<M and 0<=v[1]<N:
        if farm[v[0]][v[1]]:
            return True

def bfs(farm, start, M, N):
    queue = deque([start])
    farm[start[0]][start[1]] = 0
    while queue:
        v = queue.popleft()
        farm[v[0]][v[1]] = 0
        adjs = [(v[0], v[1]+1), (v[0], v[1]-1), (v[0]+1, v[1]), (v[0]-1, v[1])]
        for adj in adjs:
            if check_adj(farm, adj, M, N):
                queue.append(adj)
    return farm

def solution(farm):
    ans = 0
    for m in range(M):
        for n in range(N):
            if farm[m][n]:
                ans += 1
                farm = bfs(farm, (m, n), M, N)

    return ans

T = int(input())

answers = []
for _ in range(T): #for each test case
    M, N, K = map(int, input().split( ))

    #prepare farm
    farm = [[0 for _ in range(N)] for _ in range(M)]
    for _ in range(K):
        x, y = map(int, input().split( ))
        farm[x][y] = 1

    print(solution(farm))

 

수정한 부분

 

- 상하좌우 node의 범위가 0부터 M, 0부터 N 사이의 값인지 검사함.

 

틀린 원인

 

시간초과. 인접 node를 queue에 넣고, 이후에 queue에서 각 node를 pop할 때 그 값을 0으로 바꿔줬는데, BFS는 같은 depth의 node를 모두 검사한 후 그 다음 depth로 넘어가기 때문에 이렇게 하면 중복으로 queue에 값이 들어가는 경우가 생김. 

예외 케이스: https://www.acmicpc.net/board/view/84210

 

 

💡 Solution

코드

from collections import deque

def check_adj(farm, v, M, N):
    if 0<=v[0]<M and 0<=v[1]<N:
        if farm[v[0]][v[1]]:
            return True

def bfs(farm, start, M, N):
    queue = deque([start])
    farm[start[0]][start[1]] = 0
    while queue:
        v = queue.popleft()
        adjs = [(v[0], v[1]+1), (v[0], v[1]-1), (v[0]+1, v[1]), (v[0]-1, v[1])]
        for adj in adjs:
            if check_adj(farm, adj, M, N):
                queue.append(adj)
                farm[adj[0]][adj[1]] = 0
    return farm

def solution(farm):
    ans = 0
    for m in range(M):
        for n in range(N):
            if farm[m][n]:
                ans += 1
                farm = bfs(farm, (m, n), M, N)

    return ans

T = int(input())

answers = []
for _ in range(T): #for each test case
    M, N, K = map(int, input().split( ))

    #prepare farm
    farm = [[0 for _ in range(N)] for _ in range(M)]
    for _ in range(K):
        x, y = map(int, input().split( ))
        farm[x][y] = 1

    print(solution(farm))

 

코드 설명

• 모든 node에 대해 검사를 진행하여 값이 1인 경우 BFS를 이용하여 connected component들을 모두 0으로 바꿔준다.

 

주의할 점

• BFS로 connected component를 찾을 때, 상하좌우 모두를 탐색해야 한다.
• queue에 node를 넣을 때 해당 node의 값을 동시에 0으로 넣어주어야 한다. pop 한 다음 0으로 바꿔주면 그 사이에 중복으로 queue에 들어가는 값이 생긴다. 즉 queue에 넣음과 동시에 방문처리를 해 주어야 함.