[백준] 1743 파이썬(python) : 음식물 피하기

1743번 : 음식물 피하기

 

 

나의 dfs풀이)

import sys
sys.setrecursionlimit(10**5)
n, m, k = map(int, sys.stdin.readline().split())
graph = [ [0]*m for _ in range(n) ]
for _ in range(k):
    a, b = map(int, sys.stdin.readline().split())
    graph[a-1][b-1] = 1 #1
visit = [ [False]*m for _ in range(n) ] #2
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
res = 0

def dfs(x, y):
    global cnt
    for i in range(4): #3
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m:
            if graph[nx][ny] == 1 and not visit[nx][ny]: #4
                visit[nx][ny] = True
                cnt += 1
                dfs(nx, ny) #5

for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visit[i][j]: #6
            cnt = 0
            dfs(i, j)
            res = max(res, cnt) #7
print(res)

 

#1 : 그래프의 인덱스는 0번부터 시작하므로 입력받은 인덱스에 -1을 해준 인덱스에 쓰레기위 위치 표시

#2 : 방문처리할 2차원 리스트

#3 : 방향벡터 돌리면서 인접한 쓰레기를 찾기

#4 : 인접한 쓰레기 중 아직 방문처리가 되지 않은 쓰레기라면 방문처리 후 cnt+1

#5 : 새로운 위치에서 재귀호출

#6 : 그래프탐색 중 방문하지 않은 위치의 쓰레기를 발견하면 dfs시작

#7 : 가장 큰 쓰레기의 크기를 저장

 

 

나의 bfs풀이)

import sys
from collections import deque
n, m, k = map(int, sys.stdin.readline().split())
graph = [ [0]*m for _ in range(n) ]
for _ in range(k):
    a, b = map(int, sys.stdin.readline().split())
    graph[a-1][b-1] = 1 #1
visit = [ [False]*m for _ in range(n) ] #2
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
res = 0
q = deque()

def bfs(x, y):
    global cnt
    q.append((x, y)) #3
    while q:
        x, y = q.popleft() #4
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if graph[nx][ny] == 1 and not visit[nx][ny]: #5
                    visit[nx][ny] = True
                    cnt += 1
                    q.append((nx, ny))
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visit[i][j]: #6
            cnt = 0
            bfs(i, j)
            res = max(res, cnt)

print(res)

 

#1 : 그래프의 인덱스는 0번부터 시작하므로 입력받은 인덱스에 -1을 해준 인덱스에 쓰레기위 위치 표시

#2 : 방문처리할 2차원 리스트

#3 : 첫방문 위치를 큐에 저장

#4 : 큐의 가장 왼쪽 내용을 빼서 x, y로 저장

#5 : 조건에 부합하면 위치 방문처리, cnt+1, 큐에 새로운 위치 추가

#6 : 방문하지 않은 쓰레기의 위치라면 bfs실행하고 실행이 끝나면 res갱신