[BOJ] 백준 20058번: 마법사상어와 파이어스톰

date

Sep 20, 2022

slug

boj-20058

author

status

Public

문제링크

20058번: 마법사 상어와 파이어스톰

https://www.acmicpc.net/problem/20058

문제 분석

단순 구현 + DFS

파이어스톰(격자나누기+배열돌리기+얼음삭제) ⇒ 단순 2차원배열 구현

가장 큰 얼음덩어리 칸 카운트 ⇒ DFS or BFS 사용

설계

input

N, Q
N 기반 map 생성
N 기반 map 초기화

파이어스톰 구현

for(Q)

step1) 격자 나눈 후 각 구역 내에서 배열돌리기
step2) 얼음삭제

가장 큰 얼음덩어리 크기 출력

파이어스톰 구현(시뮬레이션)

배열돌리기를 함수로 모듈화하였음

시작 위치 인덱스와 배열 사이즈를 넣으면 해당 범위만 접근하여 배열 돌리기 수행

파이어스톰 함수 내에서 for문을 통해 사이즈에 맞게 격자를 나누어

각 격자의 시작인덱스를 배열돌리기 함수 인자로 전달하여 해당 격자 배열 돌리기

Step 1) 격자 나눈 후 각 구역 내에서 배열돌리기

//격자 나누기


for(int i = 0; i < 한 행에서의 격자개수; i += 격자 사이즈) {
	for(int j = 0; j < 한행에서의 격자개수; j += 격자 사이즈) {
		해당 격자의 시작 위치 인덱스 = (i, j)
		배열돌리기(i, j, 격자사이즈);
	}
}

//배열 돌리기

N*N 행렬을 행 단위로 시계 방향으로 회전하는 방법

step 1) 전치행렬 : A_(x, y) ↔ A_(y, x) 두 대칭되는 원소 Swap

step 2) 좌우반전

N*N 행렬을 행 단위로 반시계 방향으로 회전하는 방법

step 1) 전치행렬 : A_(x, y) ↔ A_(y, x) 두 대칭되는 원소 Swap

step 2) 상하반전

N*N 행렬을 한 칸씩 시계 방향/반시계 방향으로 회전하는 방법

모든 방향에 대하여 사이즈만큼 for 문 돌기

for( 왼 → 오 )
for( 위 → 아래 )
for( 오른 → 왼 )
for( 아래 → 위 )

이때 주의: 덮어쓰기이므로 for문 진행방향과 반대 방향으로 덮어쓰기

Step2) 얼음 삭제

//삭제할 노드 체크 및 기억

주의) 인접노드 탐색하며 삭제 여부 확인해야하므로 실시간으로 삭제X

→ List 에 추가해두고 탐색 끝낸 후 일괄 삭제

모든 각 노드에 대하여

가지치기1) 현재 칸의 얼음이 0이면

탐색 아예 필요 없음(얼음 삭제 불가)

가지치기2) 현재칸이 모서리면

어차피 인접노드 2개이므로 삭제 후보에 추가

상하좌우 中 유효하고 얼음이 있는 인접 노드의 개수 세기

2개 이하라면 삭제 후보에 추가

후보 리스트에 있는 모든 노드에 대하여 얼음 1개씩 줄이기

DFS → 가장 큰 덩어리 출력

가장 큰 덩어리 값 찾으며 크기 갱신해야 하므로 maxSize = 0; 초기화

MIN_VALUE; 로 해도 되지만 어차피 0 이상일 것이므로 0으로 초기화

각 노드에 대하여 DFS 수행

현재 노드 DFS 시행 결과 사이즈(DFS 재귀호출 횟수)와 현재 maxSize 비교하여 갱신

얼음의 총 수

이중for문 돌며 카운트