[백준/1743/파이썬] 음식물 피하기

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

1743번: 음식물 피하기

 

조건

- 음식물들은 근처에 있는 것끼리 뭉치게 돼서 , 큰 음식물 쓰레기가 된다.

-  N*M 행렬, 음식물 쓰레기의 좌표가 입력됨.

 

입력

- Test 케이스

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

Output:4

SOL)

이 문제에서 핵심은 음식물 쓰레기가 모여있다는 개념을 잘 이해하는거다.

테스트 케이스에서, 아래와 같은 상황일 때, 큰 음식물 사이즈는 4라고 했기 때문에,  마치 테트리스의 _- 모양도 모여있다고 판정이남. 더 예시를 들어보자.

위와 같이 있으면, 

각각 4개, 6개 일것이다. 즉 , 음식물 쓰레기들이 연달아서 몇개 있냐 == 음식물 쓰레기의 크기 

 

Psedo Code

1.N*M 행렬을 다 탐색하긴 해야한다. - 완전 탐색을 해야함.
2.N*M 행렬에서, 음식물 쓰레기의 값이 연달아 있다면, 그 크기를 구하면 된다. 
3.음식물이 있는곳을 '1'로 나타내서, 연달아있는 '1'의 크기를 구하면 되지않을까?
4.DFS,BFS 둘 다 이용이 가능할거 같다.

 

Code

#DFS
import sys
sys.setrecursionlimit(10000) 

dy=(0,1,0,-1) # 상대좌표, 오른쪽, 위쪽 , 왼쪽 , 아래쪽 
dx=(1,0,-1,0)

N,M,k = map(int,input().split())
board=[[0]*M for _ in range(N)]
v_chk=[[False]*M for _ in range(N)]

def is_valid_coord(y,x):
    return 0<=y<N and 0<=x<M

# r-1,c-1은 , 위치는 좌표값 -> 행렬은 index
for i in range(k):
    r,c = map(int,input().split())
    board[r-1][c-1] = 1
#2차원 맵으로, 표현!

def dfs(y,x,size):
    for k in range(4):
        ny= y+dy[k] 
        nx= x+dx[k]
        if is_valid_coord(ny,nx) and not v_chk[ny][nx] and board[ny][nx]==1:
            v_chk[ny][nx] = True
            size=dfs(ny,nx,size+1)
            #print("size:",size)
    return size
***
ans=[]
#print(board)

for i in range(N):
    for j in range(M):
        if board[i][j]==1:
            v_chk[i][j]=True
            ans.append(dfs(i,j,1))

print(max(ans))