[백준][Python] 1926번 그림 - DFS,BFS

✅ 문제 링크

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

 

 

 

 

✅ 문제 파악

BFS 기본 문제 (❁´◡`❁)
도화지에 1로 연결된 구간(상하좌우)를 한 그림이라고 정의했을 때,
그림의 개수를 구하고, 가장 큰 그림의 넓이를 출력한다. (예외처리 필요)

 

 

✅ 접근 방법

 

visited -> 방문 여부를 확인하기 위한 2차원 배열
dxs, dys -> 상하좌우 방향을 표현하기 위한 리스트

can_go 함수의 조건
1. 주어진 좌표가 그래프 범위 안에 존재해야함
    0<=x<n and 0<=y<m
2. 방문하지 않았어야 함
3. graph[x][y] == 1이여야 함

bfs 함수 정의
1. queue를 만들고, 시작 좌표를 큐에 넣는다.
2. 큐가 빌 때까지 다음을 반복
   - 큐에서 좌표 (a,b)를 꺼냄
   - 상하좌우 방향으로 이동할 좌표(new_x, new_y)를 확인
   - 해당 좌표가 can_go 함수에 만족한다면? 
      -> 방문처리 후 큐에 넣기 ! 
      -> 방문한 노드의 개수(count)를 1 증가
3. 최종적으로 방문한 노드의 개수 반환

최종 ! 
1. 그래프의 모든 좌표를 순회하면서, can_go에 만족하는 좌표 찾기
2. 해당 좌표에 bfs함수를 호출하여 arr리스트 저장
3. arr리스트의 길이와 최댓값 출력 (arr리스트 길이가 0일 때 예외처리 필요)

 

 

 

 

 

 

✅ 코드 구현

import sys
from collections import deque

n,m = map(int,input().split())

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

# 방문 여부 체크 그래프
visited = [[False for _ in range(m)] for _ in range(n)]

# 상하좌우 방향 정의
dxs,dys = [0, 0, 1, -1], [1, -1, 0, 0]

# 주어진 좌표에서 이동할 수 있는지 확인하는 함수
def can_go(x,y):
		# 그래프의 범위 내에 있고, 방문하지 않았으며, 값이 1인 경우 True 반환
    return 0<=x<n and 0<=y<m and not visited[x][y] and graph[x][y]==1

def bfs(x,y):
    count = 1  # 그림 크기 1로 초기화
    q = deque() 
    q.append((x,y)) # 시작 좌표 큐에 추가

    while q:
        a,b = q.popleft()

        for dx,dy in zip(dxs,dys):
            new_x, new_y = a+dx, b+dy # 상하좌우 방향으로 이동한 좌표

            if can_go(new_x,new_y):
                count += 1  # 그림의 크기 증가
                visited[new_x][new_y] = True # 방문 처리
                q.append((new_x,new_y)) # 큐에 추가

    return count  # 그림의 최종 크기 반환

arr = []

for i in range(n):
    for j in range(m):
        if can_go(i,j) :
            visited[i][j] = True # 시작 좌표 방문 처리
            arr.append(bfs(i,j)) 

# 그림이 하나도 없는 경우 예외처리
if len(arr) == 0:
    print(len(arr))
    print(0)
else:
    print(len(arr)) # 그림의 개수
    print(max(arr)) # 가장 큰 그림

 

 

📌배우게 된 점

BFS의 구현 코드를 복습하며, BFS의 초초초초 기본 문제를 구현해보았다 !

조금 더 시간을 들여 공부해야할 것 같다