[python3] 음식물피하기 DFS문제풀이

음식물 피하기 성공다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

12956

6050

4865

46.815%

문제

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

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

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

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

입력

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

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

출력

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

예제 입력 1 복사

3 4 5
3 2
2 2
3 1
2 3
1 1

예제 출력 1 복사

4

힌트

# . . .
. # # .
# # . .

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

 

첫번째 풀이:

def dfs(x,y):

    graph[x][y]='.'

    global cnt

    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if -1<nx<N and -1<ny<M:
            if graph[nx][ny]=='#':
                graph[nx][ny]='.'
                cnt+=1
                dfs(nx,ny)

    return cnt



N,M,K=map(int,input().split())

#상하좌우로 이동

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

cnt=1
# 0으로 초기화 된 2차원 배열생성
graph=[['.']*M for _ in range(N)]

#해당하는 영역에 쓰레기표시
for i in range(K):
    x,y=map(int,input().split())
    graph[x-1][y-1]='#'

trash=[]

for i in range(N):
    for j in range(M):

        if graph[i][j]=='#':
            dfs(i,j)
            trash.append(cnt)
            cnt=1


print(max(trash))

 

 

다음과 같은 오류가 발생하였다.

 

"""

python의 기본 재귀 깊이가 1000으로 설정돼 있기 때문에 (그 이상은 RecursionError를 raise합니다) setrecursionlimit()으로 설정해주면 됩니다. 이 문제는 입력이 많은 줄로 이루어져 있어 sys.stdin.readline으로 입력을 받아들이면 훨씬 빠르게 입력받을 수 있습니다. 별개의 문제입니다."""

 

피득백을 받고 

 

import sys

sys.setrecursionlimit(10**4)    # recursion limit 제한 설정 

 

제한설정을 좀더 늘려주었다.

 

두번째풀이 , 정답

 

import sys
sys.setrecursionlimit(10**4)	# recursion limit 제한 설정

def dfs(x,y):

    graph[x][y]='.'

    global cnt

    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if -1<nx<N and -1<ny<M:
            if graph[nx][ny]=='#':
                graph[nx][ny]='.'
                cnt+=1
                dfs(nx,ny)

    return cnt



N,M,K=map(int,input().split())

#상하좌우로 이동

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

cnt=1
# 0으로 초기화 된 2차원 배열생성
graph=[['.']*M for _ in range(N)]

#해당하는 영역에 쓰레기표시
for i in range(K):
    x,y=map(int,input().split())
    graph[x-1][y-1]='#'

trash=[]

for i in range(N):
    for j in range(M):

        if graph[i][j]=='#':
            dfs(i,j)
            trash.append(cnt)
            cnt=1


print(max(trash))