[Boj/백준] 1743 Python

문제출처: https://www.acmicpc.net/problem/1743

1743번: 음식물 피하기

 

 

1. 문제 접근 방식

bfs를 돌리면서 칸마다 count값을 증가시키고 반환한다.

반환값을 리스트에 붙이고 마지막으로 리스트 원소 중 가장 큰 값을 출력한다.

 

 

2. 내가 푼 코드

import sys
from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    graph[x][y] = 0

    cnt = 1
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx < 0 or ny < 0 or nx>=n or ny>=m:
                continue
            if graph[nx][ny] == 1:
                cnt+=1
                graph[nx][ny] = 0
                queue.append((nx,ny))
    return cnt

n,m,k = map(int,sys.stdin.readline().split())

graph=[]

for _ in range(n):
    graph.append([0]*m)

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

result=[]

for i in range(n):
    for j in range(m):
        if graph[i][j]==1:
            result.append(bfs(i,j))
            

print(max(result))

 

 

3. 결과 및 느낀점

자꾸 틀렸는데 왜 틀렸는지 몰랐었는데 ny>=n이라고 해서 틀렸다.

범위를 꼭 체크하자.