[알고리즘/BFS & DFS] 1926번 : 그림 - python

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

1926번: 그림

 

---

• 문제
• 소요시간: 연습문제

---

• 설계하기(접근방법) 

1. 입력받기

행, 열의 개수와

이차원 배열을 입력받는다

 

2. 구현하기

BFS 구현을 연습해본다

 

3. 출력하기

 

 

---

• 코드(출력)

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)]
result = []

def bfs(x,y):
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0 ,0]
    count = 1
    q = deque()
    q.append([x,y])
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m:
                if visited[nx][ny] == False and graph[nx][ny] == 1:
                    visited[nx][ny] = True
                    count += 1
                    q.append([nx, ny])
    return count


for x in range(n):
    for y in range(m):
        if visited[x][y] == False and graph[x][y] == 1:
            visited[x][y] = True
            picture = bfs(x,y)
            result.append(picture)

if len(result) == 0:
    print(0)
    print(0)
else:
    print(len(result))
    print(max(result))

---

• 얻어갈 부분

1. 이중배열을 받을 때 [list(map(int, input().split())) for _ in range(n)]으로 받자

2. bfs 내에 dx dy를 상하좌우 형태 즉

0 0 -1 1

1 -1 0 0 로 선언하자

3. 큐를 선언해주고, 큐에 가장 처음 케이스를 append 해준다

4. 큐가 빌 때까지의 조건으로 while문을 선언해준다

5. 현재 들어온 x,y를 상하좌우 탐색하나

6. 범위 내에 있고, 방문하지 않았다면 탐색해주고, 방문처리한디