백준 1743번 : 음식물 피하기 (by python) - BFS

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

 

문제를 보고 바로 BFS를 이용해 상하좌우에 이어진 쓰래기를 탐색해 최대(Max)를 구하면되겠다고 생각했다.

 

처음 코드 (메모리 초과)

from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
result = 0
n, m, k = map(int, input().split())
trash = [[False]*m for _ in range(n)]
for _ in range(k):
    x, y =map(int, input().split())
    trash[x-1][y-1] = True

def bfs(x, y):
    cnt = 0
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        trash[x][y] = False
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and trash[nx][ny]:
                q.append((nx, ny))
    return cnt


for i in range(n):
    for j in range(m):
        if trash[i][j]:
            result = max(bfs(i, j), result)

print(result)

 

trash 배열을 전부 만들어 trash가 있는 위치를 입력받을 때 True를 넣어 위치를 표시하고 BFS 탐색을 진행했다.

테스트 케이스는 맞출 수 있었지만, 메모리 초과가 발생했다.

 

실패 원인

문제의 원인은 조건에 맞아 큐에 추가할 때 trash방문처리를 해주지 않고 queue에서 pop 이후에 처리해주기 때문에 발생했다.

하지만,,, 이 사실을 모르던 나는 M, N의 크기가 너무 큰 입력이 들어와 배열이 크게 만들어지나 생각했다.

조건

물론... 조건을 자세히 보면 그럴일은 없지만 .. 쉬운문제라고 생각해 문제를 쓱 훓고 바로 풀이에 들어간 점이 문제였다.

 

그래서 생각해낸 방법이 배열을 만들지 않고 해결하기였다.

 

 

정답 코드(Set 이용)

from collections import deque
import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
result = 0
n, m, k = map(int, input().split())
trash = set()

for _ in range(k):
    x, y = map(int, input().split())
    trash.add((x-1, y-1))

def bfs(x, y):
    cnt = 0
    q = deque()
    q.append((x, y))
    trash.remove((x, y))  # 방문한 좌표를 trash 집합에서 제거
    while q:
        x, y = q.popleft()
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (nx, ny) in trash:
                q.append((nx, ny))
                trash.remove((nx, ny))  # 방문한 좌표를 즉시 제거
    return cnt

for x, y in list(trash):  # 집합을 순회하면서 bfs 실행
    if (x, y) in trash:
        result = max(result, bfs(x, y))

print(result)

Set을 이용해 trash를 담고 현재 좌표가 trash안에 있는지 확인하는 방식으로 구현했다.

(이때는 또 큐에 넣고 바로 방문 처리..)

 

이렇게 해결하고 이전 코드 문제점을 찾기 위해 한줄씩 꼼꼼히 뇌에서 코딩해본결과... 큐에 방문했던 좌표를 다시 넣을 수 있게된다는 사실을알고 고쳤다.

 

처음 풀이의 개선

from collections import deque
import sys
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
result = 0
n, m, k = map(int, input().split())
trash = [[0]*m for _ in range(n)]
for _ in range(k):
    x, y =map(int, input().strip().split())
    trash[x-1][y-1] = 1

def bfs(x, y):
    cnt = 0
    q = deque()
    q.append((x, y))
    trash[x][y] = 0  
    while q:
        x, y = q.popleft()
        cnt += 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and trash[nx][ny]:
                trash[nx][ny] = 0  # 방문 표시를 0으로 변경하여 다시 탐색되지 않도록 함
                q.append((nx, ny))
    return cnt

for i in range(n):
    for j in range(m):
        if trash[i][j]:
            result = max(bfs(i, j), result)

print(result)

 

 

느낀점

쉬운 문제라도 문제와 조건을 꼼꼼히 읽고 시간복잡도와 메모리를 신경써서 풀이를 진행해야겠다.