[파이썬] 1743. 음식물 피하기

문제

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

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

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

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

입력

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

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

출력

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

예제 입력 1 

3 4 5

3 2

2 2

3 1

2 3

1 1

예제 출력 1 

4

힌트

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

 

 

👸 나의 풀이

 

import sys
from collections import deque

N, M, K = map(int, sys.stdin.readline().split())  # 세로, 가로, 쓰레기 개수
junk=[["."]*M for _ in range(N)]	# 초기화

# 쓰레기 입력
for _ in range(K) :
    X, Y= map(int, sys.stdin.readline().split())
    junk[X-1][Y-1]="#"	

def bfs(i, j):
    que = deque()
    que.append((i, j))
    cnt=0
    while que:
        x, y = que.popleft()
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:		# 우좌하상 
            if 0 <= x + i < N and 0 <= y + j < M:	# 범위 체크
                if junk[x + i][y + j] == "#":
                    que.append((x+i, y+j))
                    junk[x+i][y+j]="."		# 방문 표시
                    cnt+=1
    return 1 if cnt == 0 else cnt

ans=0
for i in range(N) :
    for j in range(M) :
        if junk[i][j] == "#" :
            cnt=bfs(i, j)
            if ans < cnt :
                ans=cnt
print(ans)

 

bfs를 이용한 풀이

1303 전쟁-전투와 푸는 방법이 같다.

#이면 bfs함수를 호출하고 상하좌우로 탐색한다.

탐색한 부분은 다음에 중복되지 않게 "."으로 바꿨다.

 

 

👩‍🦲 다른 사람 풀이

 

import sys
input=sys.stdin.readline

def dfs(r, c) :
    stack=[[r, c]]
    c=0
    while stack :
        x, y=stack.pop()
        if node[x][y] : node[x][y]=False	# 방문 처리
        else : continue
        if node[x+1][y] : stack.append([x+1, y])
        if node[x-1][y]: stack.append([x-1, y])
        if node[x][y+1]: stack.append([x, y+1])
        if node[x][y-1]: stack.append([x, y-1])
        c+=1
    return c
n, m, k=map(int, input().split())	# 세로, 가로, 쓰레기 개수
mx=0
node=[[False]*(m+2) for _ in range(n+2)]
for _ in range(k) :
    x, y=map(int, input().split())
    node[x][y]=True		# 쓰레기
for i in range(n+1) :
    for j in range(m+1) :
        if node[i][j] :		# 쓰레기라면
            mx=max(mx, dfs(i, j))

print(mx)

 

스택을 이용해 dfs로 구현

나는 bfs로 구현했는데 효율이 더 좋다.

input=sys.stdin.readline 부분이 인상적이다. input()으로 써서 가독성이 좋다.

가로, 세로를 2 더 크게 만든 것은 범위를 넘어가지 않게 테두리를 만든 것이다.

 

 

import sys
sys.setrecursionlimit(100000)

n, m, k=map(int, sys.stdin.readline().split())	# 세로, 가로, 쓰레기 개수

waste=[[0 for _ in range(m)] for _ in range(n)]

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

for _ in range(k) :
    r, c=map(int, sys.stdin.readline().split())
    waste[r-1][c-1]=1	# 쓰레기

check=[[False for _ in range(m)] for _ in range(n)]

def dfs(x, y) :
    global cnt
    check[x][y]=True
    if waste[x][y] == 1 :
        cnt+=1

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

        if 0 <= nx < n and 0 <= ny < m :	# 범위 체크
            if waste[nx][ny] == 1 and not check[nx][ny] :	# 방문 안한 쓰레기
                dfs(nx, ny)

result=0
for i in range(n) :
    for j in range(m) :
        if waste[i][j] == 1 and not check[i][j] :	# 방문한 적 없는 쓰레기
            cnt=0
            dfs(i, j)
            result=max(result, cnt)

print(result)

 

재귀를 이용한 dfs 구현

 

 

문제 출처 💁‍♀️ 백준