일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
- php 프로그래밍 입문 솔루션
- 자바 스프링
- 자바
- php 프로그래밍 입문 문제풀이
- C
- 스프링
- Java
- php 프로그래밍 입문 예제
- C언어
- SWEA
- php 프로그래밍
- 페이코 초대코드
- 플러터 개발환경 설정
- php
- JAVA SPRING
- 한정 분기
- 페이코 친구코드
- programmers
- php 프로그래밍 입문 연습문제
- 배열
- Flutter
- 최단 경로
- spring
- 플러터
- 파이썬
- 페이코 추천인
- php 프로그래밍 입문 3판
- php 프로그래밍 입문
- 백준
- 페이코 추천인코드
- Today
- Total
ImJay
[파이썬/Python] 백준 1018번 체스판 다시 칠하기 본문
[파이썬/Python] 백준 1018번 체스판 다시 칠하기
문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8*8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
해설
1. M * N 체스판이 있으면, 우리는 그 중 8 * 8 크기만 탐색해야 한다.
인덱스 0~7까지 탐색후 처음과 끝을 1씩 증가하면서 M, N 의 끝까지 탐색한다.
2. 그 지정한 범위의 8 * 8 안에서 인덱스를 돌면서, B인지 W인지를 체크한다.
index = 0 을 기준점으로,
시작이 W인 경우를 cnt1, 시작이 B인 경우를 cnt2로 가정하여 체크한다.
만약 짝수가 B라면면 cnt1 이 체크되고, W이면 cnt2가 체크된다.
홀수가 W라면 cnt1이 체크되고, B이면 cnt2가 체크된다.
3. cnt1, cnt2 중 최소값을 res에 저장한다.
4. res 에는 M * N 을 돌면서 나온 최소값들이 저장되어있다.
그 중에서 최소 값이 다시 칠해야하는 최소 개수이다.
코드
import sys
N, M = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(N)]
res = []
for i in range(N-7):
for j in range(M-7):
cnt1 = 0
cnt2 = 0
for k in range(i, i+8):
for l in range(j, j+8):
if (k+l) % 2 == 0:
if board[k][l] != 'W':
cnt1 += 1
else:
cnt2 += 1
else:
if board[k][l] != 'B':
cnt1 += 1
else:
cnt2 += 1
res.append(min(cnt1, cnt2))
print(min(res))
풀이
import sys
N, M = map(int, sys.stdin.readline().split())
board = [sys.stdin.readline().strip() for _ in range(N)]
res = []
1. M, N 을 입력 받고 M*N 크기의 보드를 생성한다. res 는 최소값을 저장
for i in range(N-7):
for j in range(M-7):
cnt1 = 0
cnt2 = 0
for k in range(i, i+8):
for l in range(j, j+8):
2.
i, j 는 8 * 8 의 기준을 정해주고,
k,l 은 8 * 8 의 시작점부터 끝점까지를 돌면서
W인지, B인지 체크한다.
for i in range(N-7):
for j in range(M-7):
cnt1 = 0
cnt2 = 0
for k in range(i, i+8):
for l in range(j, j+8):
if (k+l) % 2 == 0: # 짝수
if board[k][l] != 'W':
cnt1 += 1
else:
cnt2 += 1
else: # 홀수
if board[k][l] != 'B':
cnt1 += 1
else:
cnt2 += 1
3.
짝수일 경우, W가 아닐 경우 cnt1 체크, B가 아닐 경우 cnt2 체크
홀수일 경우, B가 아닐 경우 cnt1 체크, W가 아닐 경우 cnt2 체크
for i in range(N-7):
for j in range(M-7):
cnt1 = 0
cnt2 = 0
for k in range(i, i+8):
for l in range(j, j+8):
if (k+l) % 2 == 0:
if board[k][l] != 'W':
cnt1 += 1
else:
cnt2 += 1
else:
if board[k][l] != 'B':
cnt1 += 1
else:
cnt2 += 1
res.append(min(cnt1, cnt2))
4. 저장된 cnt1, cnt2 중 최소값을 res에 저장(8*8 내에서 최소값)
print(min(res))
5. M*N 내에서의 최소값 출력
피드백
Q. 고칠 필요가 없는 경우에도 카운터가 올라가지 않을까?
A. 시작이 W라 가정하고,
i=0, j=0 일 때,
첫번째 if 문에 걸려서 index1 = 0,
i=0, j=1 일 때, else 문에 걸릴거고
값은 B일테니 index1 = 0
따라서 고칠 필요가 없는 경우에도 카운터는 올라가지 않는다.
'Solved.ac - Python > CLASS 2' 카테고리의 다른 글
[파이썬/Python] 백준 1654번 랜선 자르기 (0) | 2023.04.18 |
---|---|
[파이썬/Python] 백준 1436번 영화감독 숌 (0) | 2023.04.17 |
[파이썬/Python] 백준 1259번 팰린드롬수 (0) | 2023.04.17 |
[파이썬/Python] 백준 1181번 단어 정렬 (0) | 2023.04.14 |
[파이썬/Python] 백준 1085번 직사각형에서 탈출 (0) | 2023.04.13 |