[백준] 1926번(python 파이썬)

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

 

---

처음에 DFS로 풀었지만 메모리 초과가 나왔다. 재귀에 이상이 있음을 확인하였다.

입력크기가 n(1 ≤ n ≤ 500), m(1 ≤ m ≤ 500) 이기 떄문에 재귀로 풀면 메모리 초과가 뜬다.

때문에 BFS를 사용하여 풀었다.

 

BFS (2차원배열 인접 리스트 확인 (상, 하, 좌, 우))

dx, dy를 이용하여 상, 하, 좌, 우 확인

for 문을 이용하여 2차원 배열의 모든 좌표 확인

 

1. 방문하지 않고, 배열의 값이 1일 경우 큐에 삽입하고 방문 처리를한다.

2. 큐에서 해당 좌표를 꺼내 그 좌표의 상, 하, 좌, 우를 확인한다. 상, 하, 좌, 우에 1이 있고 방문하지 않았다면 큐에 삽입후 방문처리를한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. (큐가 빌때까지)

 

---

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

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

def Bfs(cur_x, cur_y, graph, visited, count):
    queue = deque()
    queue.append((cur_x, cur_y))
    visited[cur_x][cur_y] = True

    while queue:
        pop_x, pop_y = queue.popleft()
        count += 1
        for i in range(4):
            next_x = pop_x + dx[i]
            next_y = pop_y + dy[i]

            if next_x <= -1 or next_x >= n or next_y <= -1 or next_y >= m:
                continue
            if not visited[next_x][next_y] and graph[next_x][next_y]:
                visited[next_x][next_y] = True
                queue.append((next_x, next_y))
    return count

answer_list = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 1 and not visited[i][j]:
            answer_list.append(Bfs(i, j, graph, visited, 0))

print(len(answer_list))
if not answer_list:
    print(0)
else:
    print(max(answer_list))