[백준 알고리즘] 백준 1743번 음식물 피하기 파이썬(Python)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 1743번 음식물 피하기 파이썬(Python)

1) 문제번호 : 1743번

 

2) 문제 출처

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

1743번: 음식물 피하기

 

2. 문제

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

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

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

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

 

3. 제약사항

 

 

4. 입력

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

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

 

5. 출력

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

 

6. 풀이

- 쓰레기가 있는 곳에 1로 표시하고, board에서 완전 탐색을 하는데 1이 있는 경우에 BFS를 돌린다.

- BFS를 돌리면서 4방 탐색을 하고, 1이 있으면 계속 큐에 넣어 쓰레기 개수를 1씩 증가시킨다.

- 그리고, BFS를 다 돌았으면 result와 최대 비교를 하여 최대값을 찾는다.

 

7. 소스 코드

import sys
input=sys.stdin.readline

N, M, K = map(int, input().split()) # 통로의 세로 및 가로 길이, 음식물 쓰레기 개수

# 통로
board = [[0] * M for _ in range(N)]

# 방문체크
visit = [[0] * M for _ in range(N)]

# 쓰레기 위치 입력
for _ in range(K) :
    a, b = map(int, input().split())
    board[a-1][b-1] = 1

dx = [-1,1,0,0] # 상, 하, 좌, 우
dy = [0,0,-1,1] # 상, 하, 좌, 우

queue = []
def BFS(x,y) :
    global v # 쓰레기 개수
    queue.append([x,y])
    visit[x][y] = 1
    v += 1

    while queue :
        x, y = queue[0][0], queue[0][1]
        del queue[0]


        for i in range(4) :
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<N and 0<=ny<M and visit[nx][ny] == 0 and board[nx][ny]==1:
                queue.append([nx,ny])
                visit[nx][ny] = 1
                v += 1

result = 0 # 총 쓰레기 개수
v = 0 # 쓰레기 개수
for i in range(N) :
    for j in range(M) :
        if board[i][j] == 1 :
            BFS(i,j)
            result = max(result, v) # 최대 비교
            v = 0

print(result)

 

---