백준 1743 음식물 피하기

 

import sys

sys.setrecursionlimit(10 ** 8)

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

N, M, K = map(int, input().split())
trash_map = [[False for _ in range(M)] for _ in range(N)]
check_map = [[False for _ in range(M)] for _ in range(N)]

answer = 0
size = 0

for _ in range(K):
    r, c = map(int, input().split())

    trash_map[r - 1][c - 1] = True


def err(ey, ex):
    return 0 <= ey < N and 0 <= ex < M


def search(sy, sx):
    global size

    size += 1
    check_map[sy][sx] = True

    for si in range(4):
        ny = sy + dy[si]
        nx = sx + dx[si]

        if err(ny, nx) and not check_map[ny][nx] and trash_map[ny][nx]:
            search(ny, nx)


for i in range(N):  # 줄 수
    for j in range(M):  # 칸 수
        if trash_map[i][j] and not check_map[i][j]:
            search(i, j)

            answer = max(size, answer)
            size = 0

print(answer)

 

완전탐색과 DFS를 이용해 해결했다.

 

첫번째 위치부터 마지막 위치까지 완전 탐색을 하고 음식물이 있는 위치에서부터 DFS를 시작한다.