BFS Python 문제 BOJ1926 코딩테스트 (3)

목차

서론

지난번엔 BFS 개념에 대해 포스팅을 했다. 이번에는 BFS를 이용해 문제를 풀어보고자 한다. 원래 이 포스팅에서 여러가지 풀이를 남길 생각이었으나, BFS는 하나도 벅차다. 때문에, 이 포스팅에서는 백준 BOJ1926만 풀어보도록 하겠다.

---

백준 BOJ 1926 문제 풀이 (내풀이)

내가 1926 문제를  푼 과정은 다음과 같다. 1) 너비를 알아야 됨 -> 주변부 탐색 BFS 사용. 2) 총 drawing의 개수 -> 시작점이 하나가 아니기에 모든 그래프를 훑는 for문을 만들고 + 새로운 시작점이 나올때마다 체크하는 변수 필요 3) 새로운 시작점이 생기면 그 때 while queue: 문을 도는것이니 for문 안에 while문 넣기. 4) 마지막에 max값과 현재 너비 비교 후 갱신. 해서 풀은 코드는 아래와 같다. 이렇게 간략하게 썼지만 실제로 이중for문을 어떻게 넣어야 될지, 체크는 어떻게 해야될지 몰라 시간이 꽤 걸린 문제다. 눈물남. 

 

from collections import deque

num_of_drawings = 0

max_area_of_drawings = 0

n,m = 6,5

graph = [[1, 1, 0, 1, 1]

,[0, 1, 1, 0, 0]

,[0, 0, 0, 0, 0]

,[1, 0, 1, 1, 1]

,[0, 0, 1, 1, 1]

,[0, 0, 1, 1, 1]]

visited = [[False]*m for _ in range(n)] # queue 돌 때 상하좌우 체크용

queue = deque()

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

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

for i in range(n):

    for j in range(m):

        if graph[i][j] == 1 and visited[i][j] == False: #그래프가 1표시가 돼있고 visited 아니면

            num_of_drawings += 1 # drawing 개수 +1

            queue.append((i,j))

            visited[i][j] = True

            area_of_drawing = 1 #현재 그림 면적 초기화

            while queue:

                x,y = queue.popleft()

                for k in range(4):

                    nx = x + dx[k]

                    ny = y + dy[k]

                   

                    if nx<0 or ny<0 or nx>=n or ny>=m:

                        continue

                    if visited[nx][ny] or graph[nx][ny] != 1:

                        continue

                    visited[nx][ny] = True

                    queue.append((nx,ny))

                    area_of_drawing += 1 # 한 드로잉의 면적 구하기

            if area_of_drawing>= max_area_of_drawings:

                max_area_of_drawings =area_of_drawing

           

 

---

백준 BOJ 1926 문제 풀이 (동영상 풀이)

1. 상하좌우 연결된 그림 크기 알아내고 2. 도화지에 있는 모든 그림 찾아내기 -> 2중for문 으로 해결. 이렇게 두가지로 크게 가져가는건 나와 같은 전략이다. 쓰는 언어가 달라서 이 문제 풀이는 코드 과정만 알아보도록 하겠다. 처음에 변수 n,m 과 dx,dy, max, num(그림의수)를 선언한 뒤, 2중 for 문을 돌며 vis안한곳이 있다면 그림의 수를 +1해줬다. 그리고 방문한곳을 체크한 뒤, 해당 값을 queue에다가 넣었다. queue에 넣을때 area를 0으로 갱신했음. 이후 익숙한 bfs에 넣었다. 마지막으로는 max값은 max(mx,area)로 하여 최대값을 체크했다.

 

끝으로

이번 포스팅에서는 백준 BOJ1926에 대해 파이썬 풀이법과 그 과정을 알아보았다. 다음포스팅에서는 백준 BOJ2178 미로 탐 문제를 풀어볼 예정이다. 코딩 테스트 관련 계획과 일지를 보시려면 여기로.

코딩 테스트 준비 계획