[알고리즘][Python] 백준(BOJ) 1743 음식물 피하기_파이썬

 

1743 음식물 피하기    https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

 

 

 

 

 

 

문제 풀기 전 공부할 것 : 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

 

 

풀이 1

<내용>

• 음식물을 waste에 입력받는다.
• idx 리스트에 음식물 위치를 저장한다.
• check 리스트를 만들어 이미 뭉친 음식물인지 아닌지 판별한다.
• idx 리스트가 비어질 때까지 while문을 반복한다.
• 음식물 위치를 pop 해서 만약에 이미 뭉친 음식물이라면 while문으로 돌아간다.
• 뭉친 음식물이 아니라면 new_idx 리스트에 넣고 인접한 곳을 돌면서 음식물을 뭉치고 가장 큰 음식물 쓰레기를 res에 저장한다.

 

 

<코드>

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
waste = [[0 for _ in range(m)] for _ in range(n)]
idx = []

for _ in range(k):
    r, c = map(int, input().split())
    waste[r-1][c-1] = 1
    idx.append((r-1, c-1))
    
res = 0
check = [[False for _ in range(m)] for _ in range(n)]
while idx:
    i, j = idx.pop()
    if check[i][j]:
        continue
    cnt = 1
    check[i][j] = 1
    new_idx = [(i, j)]
    while new_idx:
        i, j = new_idx.pop()
        for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= x < n and 0 <= y < m:
                if not check[x][y] and waste[x][y] == 1:
                    check[x][y] = 1
                    cnt += 1
                    new_idx.append((x, y))
    res = max(res, cnt)
    
print(res)

 

+) dfs로 해결하기

 

 

 

 

 

 

 

 

풀이 2

<내용>

• 위의 방법을 dfs로 해결하기
• python은 최대 재귀 깊이를 늘리도록 설정해야 런타임 에러가 뜨지 않는다.
  • sys.setrecursionlimit(숫자)

 

 

<코드>

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

n, m, k = map(int, input().split())
waste = [[0 for _ in range(m)] for _ in range(n)]
for _ in range(k):
    r, c = map(int, input().split())
    waste[r-1][c-1] = 1

check = [[False for _ in range(m)] for _ in range(n)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dfs(x, y):
    global cnt
    check[x][y] = True
    if waste[x][y] == 1:
        cnt += 1
        
    for idx in range(4):
        nx, ny = x+dx[idx], y+dy[idx]
        if 0 <= nx < n and 0 <= ny < m:
            if waste[nx][ny] == 1 and not check[nx][ny]:
                dfs(nx, ny)

res = 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)
            res = max(res, cnt)
print(res)