백준 1743 음식물 피하기 Python 3

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

1743번: 음식물 피하기

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ1743.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys
sys.setrecursionlimit(10001)
input = sys.stdin.readline

def dfs(x, y):
    global size
    size += 1
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        if 1 <= nx <= M and 1 <= ny <= N and graph[ny][nx] and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

N, M, K = map(int, input().split())
graph = [[0]*(M+1) for _ in range(N+1)]
for _ in range(K):
    y, x = map(int, input().split())
    graph[y][x] = 1
visit = [[0]*(M+1) for _ in range(N+1)]
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = 0

for y in range(1, N+1):
    for x in range(1, M+1):
        if graph[y][x] and not visit[y][x]:
            global size
            size = 0
            visit[y][x] = 1
            dfs(x, y)
            if answer < size: answer = size
print(answer)

---

풀이 과정

풀이 시간 8분

import sys
#최대 100x100이므로 재귀 제한을 늘려준다
sys.setrecursionlimit(10001)
input = sys.stdin.readline

def dfs(x, y):
	#음식물 크기 1 증가
    global size
    size += 1
    
    #인접한 4방향 탐색
    for ddx, ddy in zip(dx, dy):
        nx = x+ddx
        ny = y+ddy
        #범위 안에 있으면서 음식물이 있는 칸이면서 이전에 방문한적 없다면, 탐색한다
        if 1 <= nx <= M and 1 <= ny <= N and graph[ny][nx] and not visit[ny][nx]:
            visit[ny][nx] = 1
            dfs(nx, ny)

#입력 받기
N, M, K = map(int, input().split())
graph = [[0]*(M+1) for _ in range(N+1)]
for _ in range(K):
    y, x = map(int, input().split())
    #음식물이 있는 위치 1로 설정
    graph[y][x] = 1
    
visit = [[0]*(M+1) for _ in range(N+1)]
#좌 상 우 하
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
answer = 0

for y in range(1, N+1):
    for x in range(1, M+1):
    	#이전에 방문한 적 없으면서 음식물이 있는 위치라면 dfs 탐색을 시작한다
        if graph[y][x] and not visit[y][x]:
            global size
            #음식물 크기 초기화
            size = 0
            visit[y][x] = 1
            dfs(x, y)
            #현재 음식물 크기가 이전 음식물보다 큰 경우, answer 갱신
            if answer < size: answer = size
            
print(answer)

#시간복잡도 = O(V+E), 공간복잡도 = O(n)