https://www.acmicpc.net/problem/2583
문제
입력
풀이
처음에는 좌표로 왼쪽 아래에서 시작해야할 것 같아서 이 그림을 어떻게 뒤집을까 고민했는데
생각해보니 왼쪽 위에서부터 시작하면 그냥 아래에 거울 둔것처럼 뒤집히기 때문에 영역(너비)구하는데에는 무리가 없어서 2차원 배열로 풀어줬음!
사용 알고리즘 : BFS
이 문제를 처음 보자마자 든 생각은 좌표에 해당하는 직사각형 너비는 다 1로 만들어주고 직사각형 너비에 해당하지 않는 부분은 0으로 만들어주면 BFS의 대표적인 미로찾기 문제처럼 0과 1로 이루어진 좌표를 만들 수 있었음. 여기서는 겹치는 부분도 존재했기 때문에 직사각형 너비에 대한 부분은 +1씩 해줬음.
나는 BFS 알고리즘을 풀 때 기본적인 BFS함수의 틀을 만들어놓고 시작한다.
def bfs(x, y):
cnt = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
queue = deque()
queue.append((x, y))
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 >= len(ground) or ny >= len(ground[0]):
continue
if ground[nx][ny] >= 1:
continue
if ground[nx][ny] == 0:
ground[nx][ny] = 1
queue.append((nx, ny))
cnt += 1
if cnt == 0 :
cnt = 1
return cnt
- 여기서는 다른 BFS문제들과 달리 좌표의 값이 0일 경우에만 방문처리를 해주고 cnt를 활용해서 너비를 구해줬음
- 마지막에 if문에서 자꾸 너비가 1인 애의 너비가 0으로 나와서 넣어준 것인데 .. 다른 처리가 필요하다고 생각하는데 아무나 지적해주세요
전체코드
from collections import deque
N, M, K = map(int, input().split())
rectangle_list = list()
ground = [[0 for col in range(M)] for row in range(N)]
def bfs(x, y):
cnt = 0
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
queue = deque()
queue.append((x, y))
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 >= len(ground) or ny >= len(ground[0]):
continue
if ground[nx][ny] >= 1:
continue
if ground[nx][ny] == 0:
ground[nx][ny] = 1
queue.append((nx, ny))
cnt += 1
if cnt == 0 :
cnt = 1
return cnt
for _ in range(K):
x1, y1, x2, y2 = map(int, input().split())
rectangle_list.append([[x1, y1], [x2, y2]])
for i in range(K):
for j in range(rectangle_list[i][0][1], rectangle_list[i][1][1]):
for k in range(rectangle_list[i][0][0], rectangle_list[i][1][0]):
ground[j][k] += 1
result = list()
for i in range(N):
for j in range(M):
if ground[i][j] == 0:
result.append(bfs(i, j))
result = sorted(result)
print(len(result))
for i in range(len(result)):
print(result[i], end=' ')
- rectangle_list: [[직사각형 시작점], [직사각형 끝점]]
- ground: 직사각형을 표시하기 위한 2차원 리스트, 너비도 구해주기 위한 리스트
- ground의 값이 0일 경우에만 방문해서 bfs로 너비 구해줌
'Coding Test > 스터디' 카테고리의 다른 글
[BFS&DFS] 프로그래머스_미로찾기 (0) | 2023.11.15 |
---|---|
[DFS&BFS] 백준_1303_전쟁전투 (0) | 2023.11.15 |
[1주차] 스터디 시작 및 완전탐색 (0) | 2023.11.15 |