[python] 백준 - 1743. 음식물 피하기

🤔문제 해결

S1 | BFS

이번에는 2차원리스트를 활용하지 않고 set()을 활용하여 문제를 해결했다.

 

각각의 좌표가 주어져 있으므로 쓰레기를 하나 선택해 상하좌우 BFS탐색을 한다.

주변의 쓰레기를 선택할 때마다 visited 에 add 해준다.

또 count + 1 을 해줘서 쓰레기 더미의 크기를 answer 에 담는다.

 

💨 set() 을 쓰는 이유
 if tmp in set() : 이렇게 tmp가 set()에 있는지 없는지 확인할 때 시간복잡도가 O(1) 이다.
하지만 if tmp in list : list의 경우 O(n) 이다.

 

💻소스 코드

import sys
from collections import deque


def bfs(x, y):
    q = deque()
    q.append((x, y))
    cnt = 1  # 시작한 쓰레기 포함
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if 1 <= nx < N + 1 and 1 <= ny < M + 1:
                if (nx, ny) in trashSet and (nx, ny) not in visited:
                    cnt += 1
                    q.append((nx, ny))
                    visited.add((nx, ny))
    else:
        answer.append(cnt)


if __name__ == "__main__":
    N, M, K = map(int, sys.stdin.readline().split())

    # set() 을 쓰는 이유
    # if tmp in set(): 이렇게 tmp가 set()에 있는지 없는지 확인할 때 시간복잡도가 O(1)이다.
    # 하지만 if tmp in list: list의 경우 O(n)이다.
    trashSet = set()  # 음식물 셋
    visited = set()  # 방문 체크

    for _ in range(K):
        r, c = map(int, sys.stdin.readline().split())
        trashSet.add((r, c))

    answer = []
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    for trash in trashSet:
        if (trash[0], trash[1]) not in visited:  # 방문하지 않았따면
            visited.add((trash[0], trash[1]))  # 방문 추가
            bfs(trash[0], trash[1])  # BFS GOGO!

    print(max(answer))

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

1743번: 음식물 피하기

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다. 

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ 10,000)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

힌트

# . . .
  . # # .
  # # . .
위와 같이 음식물이 떨어져있고 제일큰 음식물의 크기는 4가 된다. (인접한 것은 붙어서 크게 된다고 나와 있음. 대각선으로는 음식물 끼리 붙을수 없고 상하좌우로만 붙을수 있다.)