✅ BOJ 문제 풀이
🎈 2563 색종이
가로, 세로 크기가 각 100인 도화지가 있고 이 위에 가로 세로 크기가 10인 정사각형 모양의 검은색 종이를 도화지와 평행하게 붙일 때 도화지 내 검은 영역의 넓이를 구하는 문제
- 첫째 줄에 색종이 수가 주어지고 둘째 줄부터 색종이를 붙인 위치가 2개의 자연수로 주어진다. 첫번째 자연수는 색종이의 왼쪽 변과 도화지 왼쪽 변 사이 거리, 두번째 자연수는 색종이 아래쪽 변과 도화지 아래쪽 변사이의 거리를 나타내므로 즉 검은색 색종이의 좌측 아래 코너에 있는 위치 값을 의미한다. 단 색종이가 도화지 범위를 벗어나는 경우는 없다.
import sys
input = sys.stdin.readline
whiteboard = [[0 for _ in range(100)] for _ in range(100)]
n = int(input())
for _ in range(n):
x, y = map(int, input().split())
for i in range(x, x + 10):
for j in range(y, y + 10):
whiteboard[i][j] = 1
answer = 0
for i in range(100):
for j in range(100):
if whiteboard[i][j]:
answer += 1
print(answer)< 풀이 과정 >
전체 도화지 넓이 - 색종이 없는 부분을 처리해주려면 고려 해주어야할 사항이 많아 구현하기 힘들다고 판단했고, 빈 도화지를 만들어 검은색 영역을 칠해 칸에 값이 있으면 영역 넓이 + 1 해주는 방식을 생각했다.
- 빈 2차원 array를 [0,99]로 만들고 입력받는 x,y값에 10까지 더해준 값들을 array에 입력하여 추후 값이 존재하면 영역 넓이를 더해주는 방식으로 진행했다.
🎈 2167 2차원 배열의 합
입, 출력이 위와 같고, 2차원 배열 내 (i,j) ~ (x,y) 칸으로 이동하면서 접하는 값들을 모두 더해 출력하는 문제
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
matrix = []
for i in range(n):
matrix.append(list(map(int, input().split())))
k = int(input())
for _ in range(k):
i, j, x, y = map(int, input().split())
answer = 0
for w in range(i-1, x):
for z in range(j-1, y):
answer += matrix[w][z]
print(answer)< 풀이 과정 >
문제 내용 그대로 구현해주기 위해 빈 matrix 리스트를 생성하고 for문으로 n줄만큼 list를 append하여 2차원 리스트를 구성한 후 k줄 만큼 입력받는 i,j,w,x 정보를 이용해 2중 포문으로 값을 더해 출력해주는 코드를 작성하였다.
그러나, 3중 포문이라는 비효율적인 코드로 인해 시간 초과를 피하지 못했고 이를 해결하고자 dp를 사용하려 한다.
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
k = int(input())
for _ in range(k):
i,j,x,y = map(int, input().split())
answer = 0
answer += dp[x][y] - dp[i-1][y] - dp[x][j-1] + dp[i-1][j-1]
print(answer)< 풀이 과정 >
dp라는 행 m+1, 열 n+1개로 구성된 2차원 배열을 만든다. 이 dp에는 이동 시 더한 결과값을 나타내주기 위해 다음과 같은 방식으로 처리한다. (좌측 대각선 위쪽에 있는 값은 중복되므로 -를 사용한다.)
dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
결과적으로, 각 (x,y)에 위치한 결과는 합이 미리 계산된 dp를 활용하여 출력한다.
🎈 2573 빙산
빙산의 높이 정보, 바다 정보가 담긴 2차원 배열을 입력값으로 받고 주변이 바다인 면 수 만큼 매년 높이가 낮아진다. 이때 최종 두 덩어리 이상 분리된 경우 걸린 년 수를 구하는 문제.
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
iceberg = [list(map(int, input().split())) for _ in range(n)]
iceland = []
for i in range(n):
for j in range(m):
if iceberg[i][j]:
iceland.append((i, j))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque([(x, y)])
visited[x][y] = 1
sea_list = []
while queue:
x, y = queue.popleft()
sea = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m:
if not iceberg[nx][ny]:
sea += 1
elif iceberg[nx][ny] and not visited[nx][ny]:
queue.append((nx, ny))
visited[nx][ny] = 1
if sea > 0:
sea_list.append((x, y, sea))
for x, y, sea in sea_list:
iceberg[x][y] = max(iceberg[x][y] - sea, 0)
return 1
year = 0
while iceland:
visited = [[0]*m for _ in range(n)]
melting = []
cnt = 0
for i,j in iceland:
if iceberg[i][j] and not visited[i][j]:
cnt += bfs(i, j)
if iceberg[i][j] == 0:
melting.append((i, j))
if cnt > 1:
print(year)
break
iceland = sorted(list(set(iceland) - set(melting)))
year += 1
if cnt < 2:
print(0)< 풀이 과정 >
경로를 매 칸마다 확인해줘야 하기에 BFS를 이용하여 문제를 풀이하였다.
풀이를 위해 여러 변수들을 지정하면서 풀었다. 다 풀고보니 지정한 변수가 너무 많은 편이라고 생각이 든다.🙄
- BFS 함수를 구성하기 전 입력 값을 변수로 지정하고 iceland라는 빙산이 존재하는 위치 정보를 담은 리스트를 만들어준다.
- 경로를 이동해가면서 주변이 바다인지 탐색하기 위해 dx, dy도 지정해주었다.
< BFS 함수 >
- BFS 함수 내에서 빙산이 위치하지 않은 곳은 바다이므로 바다 면수를 나타내는 sea 변수도 지정해준다.
- bfs함수를 통해 탐색을 진행하는데, 방문 여부 visited를 처리하여 4방향을 탐색한다. 탐색 시 정해진 범위 내에서 빙산이 없으면 sea += 1처리, 방문하지 않은 곳이면 queue에 입력하고 방문처리한다.
- 이후 빙산 옆의 바다 면 수 만큼 빙산이 녹았음을 처리하기 위해 우선 sea_list로 바다 위치를 찍어주고, 빙산 높이를 max(iceberg[x][y] - sea, 0)으로 매년 감소 시켜준다.
- 빙산이 있는 경우로 while 반복처리를 진행하여 녹은 지역을 나타내 매년 빙산이 녹은 곳을 저장하고 다음 년도 빙산 높이에 반영하고자 melting 리스트를 생성하였다.
- 덩어리를 0으로 처리하여 시작하고 매년 bfs함수를 통해 나뉜 개수만큼 덩어리를 더해 두 덩어리 이상 나뉜 경우 년수를 리턴한다.
🎈 15683 감시
스타트링크 사무실은 NXM 크기의 직사각형으로 나타낼 수 있고 K개의 1X1 크기를 가진 CCTV가 설치되어 있다. CCTV는 총 5개의 종류로 다음과 같다.
지도에서 0은 빈 칸, 1~5는 CCTV 번호, 6은 벽, 감시 가능한 영역은 #으로 나타낼 수 있다. 최종적으로 CCTV가 감시할 수 없는 사각지대의 크기를 구하는 문제
import sys
input = sys.stdin.readline
import copy
n, m = map(int, input().split())
# 북동남서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
cctv_direction = [
[],
[[0], [1], [2], [3]],
[[0, 2], [1,3]],
[[0,1], [1,2], [2,3], [3,0]],
[[0,1,2], [1,2,3], [2,3,0], [3,0,1]],
[[0,1,2,3]],]
cctv_loc = []
startlink = []
for i in range(n):
startlink.append(list(map(int, input().split())))
for j in range(m):
if startlink[i][j] in [1, 2, 3, 4, 5]:
cctv_loc.append([i, j, startlink[i][j]])
def watching(x, y, startlink, cctv_direction):
for i in cctv_direction:
nx = x
ny = y
while True:
nx += dx[i]
ny += dy[i]
if nx<0 or nx>=n or ny<0 or ny>=m:
break
if startlink[nx][ny] == 6:
break
elif startlink[nx][ny] == 0:
startlink[nx][ny] = '#'
answer = 1e9
def dfs(idx, startlink):
global answer
if idx == len(cctv_loc):
count = 0
for i in range(n):
count += startlink[i].count(0)
answer = min(answer, count)
return
tmp = copy.deepcopy(startlink)
x, y, num = cctv_loc[idx]
for i in cctv_direction[num]:
watching(x, y, tmp, i)
dfs(idx + 1, tmp)
tmp = copy.deepcopy(startlink)
dfs(0, startlink)
print(answer)< 풀이 과정 >
DFS, BruteForce를 이용하여 해결한 문제.
CCTV가 바라보는 방향으로 인해 모든 경우의 수를 다 확인하며 사각지대를 탐색해야하기에 브루트포스라고 생각했고, cctv 1개의 방향을 정한 순간 끝까지 다 확인 후 다시 체크하기에 재귀함수를 통해 DFS를 구현하였다.
전체적인 구현은, watching 함수를 통해서 감시가 되는 부분을 '#'으로 바꾸고 모든 경우의 수를 체크하는 dfs함수를 통해 구현하였다.
- 입력값
기본적으로 n, m과 전체 사무실을 나타내는 startlink, cctv 번호와 맞게 방향을 나타내도록 cctv_direction을 만들었고 cctv위치와 cctv 번호를 나타내기 위해 cctv_loc를 구성했다.
이후 기본적인 for문들로 각 위치를 저장시켜줌 - watching 함수
위치, startlink, cctv_direction을 파라미터로 받았다.
방향에 따라 이동할 수 있는 구간을 나타내기 위해 nx, ny를 사용했고 다음 칸이 범위를 벗어나거나 벽(6)이면 break, 아닌 경우 감시가 가능하므로 #으로 표기하였다. - dfs 함수
재귀를 통해 최소의 사각지대 크기를 구해야하므로 answer에 매우 큰 값을 받아 min으로 값을 줄여나가는 방법을 택했다.
idx와 startlink를 파라미터로 받아 전체 cctv에 대해 확인한 경우 0의 개수를 세어 최솟값을 리턴하도록 구성하였고, 각 cctv_loc에 저장된 위치에 따라 방향을 확인하고 다음 cctv를 탐색하기 위해 copy.deepcopy를 활용하여 startlink 객체가 어긋나지 않도록 하였다.
🎈 1244 스위치 켜고 끄기
스위치 상태는 1이 켜져있음을, 0은 꺼져있음을 나타낸다. 남학생은 1로 입력받으며 자신이 받은 수의 배수로 상태를 바꾼다. 여학생은 뽑은 숫자를 중심으로 좌우 대칭이 같으면 상태를 바꾼다. 출력 기준을 보면 스위치는 한 줄에 최대 20개까지만 출력 가능하다.
import sys
input = sys.stdin.readline
n = int(input())
switch = list(map(int, input().split()))
students = int(input())
for _ in range(students):
gender, num = map(int, input().split())
if gender == 1:
i = num
while num < n+1:
if switch[num-1] == 0:
switch[num-1] = 1
else:
switch[num-1] = 0
num += i
else:
if switch[num-1] == 0:
switch[num-1] = 1
else:
switch[num-1] = 0
i = num-2
j = num
while i >= 0 and j < n:
if switch[i] == switch[j]:
if switch[i] == 1:
switch[i], switch[j] = 0, 0
else:
switch[i], switch[j] = 1, 1
else:
break
i -= 1
j += 1
for i in range(0, n, 20):
print(*switch[i:i+20])< 풀이 과정 >
인덱싱을 활용한 리스트를 구현할 줄 아느냐를 묻는 문제이다.
- 입력값
스위치 개수인 n과 현 상태를 switch로 받고 학생 수 students변수와 학생 수 만큼 gender, num을 입력했다. - 구현
학생 수만큼 gender와 num을 입력받아서 성별이 다른 경우를 확인해준다. - 남자인 경우
i에 num을 저장하여 주어진 n 범위 내에 switch 상태가 1이면 0으로, 0이면 1로 처리하고 이를 입력받은 num 배수만큼 진행한다. - 여자인 경우
switch의 num-1번째 인덱스의 상태를 우선 바꾸어주고, i와 j를 각각 입력받은 num-2, num으로 인덱스로서 저장한다. switch의 i번째 상태와 j번째 상태 값이 동일하면 변환해주고 while문 돌면서 i는 0에 가깝게, j는 n에 가깝게 순환한다. - 출력값
20번째 마다 끊어서 다음줄로 이동시켜 출력하는 방법은 다음과 같다
print(list)형태로 한줄로 작성하는데, 범위를 지정하여 보기 좋게 출력가능한 방법.
는 list내 값들을 출력해주는 unpacking operator이므로 알아두면 좋을 것 같다.
