Po_tta_tt0
콩심콩 팥심팥 🌱
Po_tta_tt0
전체 방문자
오늘
어제
  • 분류 전체보기 (266)
    • 🐛 회고 (14)
    • 💭 생각 (2)
    • 🤸‍♀️ 내 프로젝트 (16)
      • FISH-NEWS (8)
      • MBTI 과몰입 테스트 (2)
      • twitter clonecoding with TS (4)
      • pilzagenda (2)
    • 👨‍👩‍👧‍👦 팀 프로젝트 (2)
      • 피우다 프로젝트 (0)
      • SEMO(세상의 모든 모임) (1)
      • 마음을 전하는 텃밭 (1)
      • Stackticon (0)
    • 👨‍💻 CS지식 (11)
    • ✍ 공부 (94)
      • JavaScript (21)
      • TypeScript (39)
      • Html (0)
      • CSS (2)
      • React (18)
      • NextJS (7)
      • Vue (1)
      • Python (1)
      • Django (0)
      • 개발환경 & 그 외 (2)
    • 🏄‍♀️ 코딩테스트 (99)
      • 🐍 Python (99)
    • 🐙 Git & GitHub (3)
    • 📑 오류기록 (8)
    • 📚 우리를 위한 기록 (9)
    • 수업 (3)
    • 강의 등 (2)
    • 👩‍🎓 SSAFY (0)
    • 👋 우테코 (0)

블로그 메뉴

  • 홈
  • 태그

공지사항

인기 글

태그

  • 구현
  • 백준 숨바꼭질
  • 백준 파이썬
  • 시뮬레이션
  • react-router-dom
  • 플로이드 워셜
  • Next.js
  • 파이썬 다익스트라
  • DP
  • dfs
  • 파이썬
  • 파이썬 감시 피하기
  • 문자열
  • js
  • React
  • 백준
  • bfs
  • 이분탐색
  • 자바스크립트
  • BFS + DP

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
Po_tta_tt0

콩심콩 팥심팥 🌱

[ 백준 2583 ] ( python ) 영역 구하기
🏄‍♀️ 코딩테스트/🐍 Python

[ 백준 2583 ] ( python ) 영역 구하기

2022. 6. 10. 17:33
반응형

 

📚 영역 구하기

 

문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

 

입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

 

 

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

 

예제 입력 1 복사

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

예제 출력 1 복사

3
1 7 13

 

 

✍ 접근

  • 문제를 이해하고 방법을 찾는다(여기서 막힘)
  • BFS로 탐색하며 결과를 구한다 
  • 🚨 x와 y list를 혼동하지 않게 주의

 

 

정답코드

# ✨ 구분 1
import sys
from collections import deque
input = sys.stdin.readline
M,N,K = map(int,input().split())

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

# ✨ 구분 2
board = [[0]*N for _ in range(M)]

for _ in range(K):
    x1,y1,x2,y2= map(int,input().split())
    for i in range(y1,y2):
        for j in range(x1,x2):
            board[i][j] = 1

# ✨ 구분 3      
res = []
def BFS(x,y):
    cnt = 1
    dq = deque([])
    dq.append((x,y))
    board[x][y] = cnt
    while dq:
        p = dq.popleft()
        for i in range(4):
            new_x = p[0] + dx[i]
            new_y = p[1] + dy[i]
            if 0<= new_x <M and 0<= new_y < N and board[new_x][new_y] == 0 :
                board[new_x][new_y] = 1
                cnt+=1
                dq.append((new_x,new_y))
    res.append(cnt)

# ✨ 구분 4
for i in range(M):
    for j in range(N):
        if board[i][j] == 0 :
            BFS(i,j)

# ✨ 출력
print(len(res))
res.sort()
print(*res)

구분 1

  • 기본적인 입력을 받고
  • BFS로 2중 리스트 board를 순회할 예정이서서 관련 코드도 미리 짜놓는다

구분 2 📌

  • 이 부분에서 많이 고생했다. 기본적인 사각형에서 사용되는 좌표와 2차원 배열의 위치를 비교해보고 별 짓을 다 해봤지만 어려웠다.
    답은 그냥 사각형의 특징을 이용하는 것이다. 
  • board를 설정해주고
for _ in range(K):
    x1,y1,x2,y2= map(int,input().split())
    for i in range(y1,y2):
        for j in range(x1,x2):
            board[i][j] = 1
  • for문을 통해 돌아주는데, 잘 보면 range의 크기가 x1,y1이 아니라 y1,y2 // x1,x2이e다.
    1. 가로와 세로를 잘 생각해야 한다. x가 가로축, y가 세로축인 기존 사각형에 비해 우리가 만들고자 하는 이중 리스트 사각형의 가로와 세로는 뒤바뀌어 있다
      => y range를 먼저 도는 이유
    2. 문제를 보면 x1.y1는 좌측 하단 좌표, x2,y2는 우측 상단 좌표이다
      => 더 큰 x값에서 작은 x 값을 뺀 값이 만약 3이라고 했을 때, 이 사이를 한 줄씩 돌면서 칠해줄 수 있다
      => y도 마찬가지
      => 이해가 안된다면 키보드의 텐키를 칠하는 방법을 생각해보면 된다.
      우측 상단 좌표(9)가 3,3
      좌측 하단 좌표(1)이 1,1
      이라고 생각했을 때
      3-1을 빼서 가운데를 도는 것을 3번 반복하면 == 2중 for문을 사용하면 텐키를 다 칠할 수 있다

      설명이 더 복잡한 느낌인데.. 아무튼 사각형을 한번 그려보면 이해가 될 것.

      사실 이 방법을 생각하지 못해서 고전한 사람은 나밖에 없을 것 같기는 하다 😣   
  • 아무튼 이렇게 for문을 돌면서 board[i][j]를 1로 채워준다.

 

구분 3,4

  • 단지번호붙이기 문제와 매우 유사한 방식으로 풀면 된다.
  • 이중 for문을 통해 board가 0인 부분을 찾으면
    • BFS 함수로 들어가서 board가 0인 부분의 수를 카운트해준다
    • while문이 끝나면 cnt에 세어진 수를 res로 보내면 된다

 

출력

  • 출력!

 

⭐ 배움

  • 가로 세로를 잘 구분하자

 

 

 

 

 

반응형

'🏄‍♀️ 코딩테스트 > 🐍 Python' 카테고리의 다른 글

[ 백준 10844 ] ( python ) 쉬운 계단 수  (0) 2022.06.12
[ 백준 7576 ] ( python ) 토마토  (0) 2022.06.10
[ 백준 1260 ] ( python ) DFS와 BFS  (0) 2022.06.10
[ 백준 2156 ] ( python ) 포도주 시식  (0) 2022.06.10
[ 백준 1912 ] ( python ) 연속합  (0) 2022.06.10
    '🏄‍♀️ 코딩테스트/🐍 Python' 카테고리의 다른 글
    • [ 백준 10844 ] ( python ) 쉬운 계단 수
    • [ 백준 7576 ] ( python ) 토마토
    • [ 백준 1260 ] ( python ) DFS와 BFS
    • [ 백준 2156 ] ( python ) 포도주 시식
    Po_tta_tt0
    Po_tta_tt0
    감자의 코딩하는 블로그 콩심은데 콩나고 팥심은데 팥난다

    티스토리툴바