[백준/Python] 1743번(그래프, DFS, BFS)_음식물 피하기

📌문제 유형

그래프 이론, 그래프 탐색, BFS, DFS (실버1)

 

📌문제

1743번: 음식물 피하기

 

📌나의 문제풀이

- BFS로 풀이

- map_안에서 1의 값 바꿔서 큰 값을 답으로 하려했지만, 실패해서 q.popleft()하는 횟수 cnt하여 답 도출

• 방문한 곳은 1이 아닌 값으로 바꾸어서 다시 탐색하지 않음

from collections import deque

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

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

ans = []          
q = deque()
for i in range(n):
    for j in range(m):
        if map_[i][j] == 1:
            q.append((i,j))
            cnt = 0

            while q:
                x,y = q.popleft()
                cnt += 1
                dx = [0,0,1,-1]
                dy = [1,-1,0,0]

                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0 <= nx < n and 0 <= ny < m:
                        if map_[nx][ny] == 1:
                            a = max(map_[nx][ny] + 1, map_[x][y] + 1)
                            map_[nx][ny] = a
                            map_[x][y] = a
                            q.append((nx,ny))
            ans.append(cnt)
print(max(ans))

 

📌 다른사람의 문제풀이

- BFS 풀이(풀이 방법 유사)

[BOJ / 백준] 1743번 음식물 피하기파이썬(Python) 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def bfs(i, j, trash):
    q = deque([[i, j]])
    trash[i][j] = 2  # visited
    result = 1

    while q:
        x, y = q.popleft()

        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 < nx <= n and 0 < ny <= m and trash[nx][ny] == 1:
                q.append([nx, ny])
                trash[nx][ny] = 2
                result += 1
    return result


n, m, k = map(int, input().split())
trash = [[0] * (m + 1) for _ in range(n + 1)]
answer = 0
for _ in range(k):
    x, y = map(int, input().split())
    trash[x][y] = 1

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if trash[i][j] == 1:
            ans = bfs(i, j, trash)
            answer = max(ans, answer)

print(answer)

 

- DFS 풀이

 

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

import sys
sys.setrecursionlimit(10*7)
n,m,k = map(int, sys.stdin.readline().rstrip().split())

size = 0
ans = 0

graph = [[0] * (m+1) for _  in range(n+1)]

for _ in range(k):
    x,y = map(int, sys.stdin.readline().rstrip().split())
    graph[x][y] = (1)

def dfs(x,y):
    global size

    if x <0 or x > n or y < 0 or y > m:
        return False
    if graph[x][y] == 1:
        size += 1   # 쓰레기 크기 1 증가
        graph[x][y] = 0     # 방문 처리
        # 인접 탐색
        dfs(x+1, y)
        dfs(x-1, y)
        dfs(x, y+1)
        dfs(x,y-1)

        return True
    return False

for i in range(n+1):
    for j in range(m+1):
        if dfs(i,j) == True:    # 쓰레기 탐색한 경우
            ans = max(size,ans)
            size = 0
print(ans)

 

📌 리뷰 

- 방문한 곳은 다시 방문하지 않도록 초기화하기

- 같은 변수 쓰지 않기

- 그래프 안 크기 변동이 안되면, cnt 변수 활용해서 개수 세기