📌 참고
오늘은 어쩌다보니 앞뒤로 사담이 굉장히 많은.. 글이 되었습니다..
풀이나 코드만 확인하고 싶으신 분들은 목차를 클릭해서 이동해주세요! 감사합니다 🙏
교공 알고리즘 스터디 25주차 삼성기출
20058번: 마법사 상어와 파이어스톰 | 문제 바로가기
문제풀이 (2022-03-02 WED 💻)
🤔 사담
갑자기 뜬금 없는 사진이긴 한데.. 정말 따뜻하게 봤던 드라마 <나빌레라> 에 이런 대사가 나온다
"준비될 때까지 기다리지 마. 내가 살아보니까 완벽하게 준비되는 순간은 안 오더라고. 그냥 지금 시작하면서 채워. 아끼다 뭐 된다는 말 알지? 무작정 부족해도 들이밀어."
너무도 나의 약점을 찌르는 조언이자 위로였다
나는 내 자신이 완벽하게 준비됐다고 느낄 때까지 도전하는 것을 꽤나 두려워하던 사람이었다
부딪쳐 보았을 때 내 부족함을 깨닫게 되는 것이 무서워서,
늘 완벽하고 멋진 사람으로 보이고 싶은 욕심에,
등등 여러 가지 이유로 그래왔다
알고리즘 공부할 때도 그랬다
솔직히 혼자서 풀어보려고 열어봤다가 와.. 난 아직 이건 못 풀겠다.. 싶어서 껐었는데
이후에 스터디에서 문제로 나와서 어쩔 수 없이 풀게 되고
또 그럭저럭 잘 풀어냈던 문제들이 있었다
이번 주차 문제도 그런 문제 중 하나이다
애초에 이 스터디 자체도 그랬다
혹시 내가 좋아하는 이 코딩을 못한다고 지적받을까봐,
아직은 알고리즘을 잘 몰라서,
들어갈까 말까 참 고민을 많이 했었는데 바보 같은 고민의 시간이었다
절대적으로 배움이 필요하지 않은 순간이 올까, 아닐 것이다
요즘 생각이 많아서 진짜 찐 사담을 늘어놓아봤다....
거두절미 하고 풀이로 고!
⭐ 풀이의 핵심
이 문제는 dfs나 bfs를 활용할 수 있는 구현 문제였다
- 파이어스톰 시전 (격자 나누고 회전하기 + 얼음 녹이기)
- 덩어리 탐색
크게 위와 같이 나뉘는데
👉 덩어리 탐색 부분은 dfs나 bfs를 활용하여 구현하면 되고
(크게 둘다 상관 없을 것 같아서 나는 이미 코드가 길어졌길래 그나마 간결한 dfs를 활용했다)
👉 파이어스톰에서 격자 나누고 회전하는 부분이 좀 까다로웠는데
i) divideGrid 함수로 나뉜 작은 격자의 시작 지점을 지정 해준 다음
cf) 아래 그림에서 9 -> 11 -> 13-> 15-> 25 -> 27 -> 29 -> 31 -> ... 과 같이 순서대로 지정
ii) 해당 지점부터 rotateGrid 함수를 통해 해당 격자를 회전 시켜줬다
이전 단계의 '행'이 이번 단계의 '열'이 되는 원리를 활용하여
변수 4개를 사용한 2중 for문을 사용했다
cf) 아래 그림에서 13 -> 9 -> 5 -> 1 의 예시를 보면 보다 이해하기 쉬울 것이다
👉얼음 녹이는 부분은
이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
위 조건이 무슨 말인지 알아듣는 데 시간이 걸리긴 했는데
쉽게 말해서 상하좌우 인접한 칸 중 얼음이 있는 칸의 개수를 카운트하고
그 값이 3 미만일 경우 얼음의 양을 1 감소시키면 된다
이해만 하면 구현은 쉬운 부분이었다
👉 추가로
grid를 원본에다 한 칸씩 순차적으로 업데이트 해나가면 모순이 생기는 구조이기 때문에
이번 회차의 변동 사항을 grid에 새로 업데이트 해주기 전에
지난 회차에서 썼던 원본 grid는 tempGrid에 따로 카피해서 남겨두는 것이 중요하다
🔽 코드 (C++)
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int powerN = pow(2,6); // cf) 2 <= N <= 6
int iceSum; // 남아있는 얼음 A[r][c]의 합
int maxCount; // 가장 큰 덩어리가 차지하는 칸의 개수
vector<vector<int>> tempGrid(powerN, vector<int>(powerN));
vector<vector<bool>> visited(powerN, vector<bool>(powerN));
int N, Q;
vector<vector<int>> grid(powerN, vector<int>(powerN)); // 2^N * 2^N 격자 얼음판
vector<int> L(1000); // 마법사 상어가 시전한 단계
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };
/* 파이어스톰 시전 */
void rotateGrid(int row, int col, int powerL) { // 부분 격자 회전
/*
이전 단계의 '행'이 이번 단계의 '열'이 되는 원리
1 2 3 4 13 9 5 1
5 6 7 8 14 10 6 2
9 10 11 12 15 11 7 3
13 14 15 16 16 12 8 4
*/
for (int i=row, n=col; i<row+powerL; i++, n++) {
for (int j=col, m=row+powerL-1; j<col+powerL; j++, m--) {
grid[i][j] = tempGrid[m][n];
}
}
}
void divideGrid(int powerL) { // 부분 격자로 나누기
// tempGrid에 이전 단계의 grid 저장
copy(grid.begin(), grid.end(), tempGrid.begin());
int row = 0;
int col = 0;
while (row < powerN) {
// (0,0)이 포함된 부분 격자부터 회전
rotateGrid(row, col, powerL);
// 다음 부분 격자의 시작 인덱스 찾기
col += powerL;
if (col >= powerN) {
col = 0;
row += powerL;
}
}
}
bool outOfRange(int row, int col) {
if (row < 0 || row >= powerN || col < 0 || col >= powerN) { return true; }
return false;
}
void decreaseIce() {
// tempGrid에 회전을 마친 grid 저장
copy(grid.begin(), grid.end(), tempGrid.begin());
for (int i=0; i<powerN; i++) {
for (int j=0; j<powerN; j++) {
if (tempGrid[i][j] == 0) {
continue;
}
int count = 0; // 얼음이 있는 인접한 칸의 개수
for (int k=0; k<4; k++) {
int nr = i + dr[k];
int nc = j + dc[k];
if (!outOfRange(nr, nc) && tempGrid[nr][nc] != 0) {
count++;
}
}
// 얼음이 있는 칸 3개 이상과 인접하지 않은 칸의 얼음의 양 1 감소
if (count < 3) {
grid[i][j]--;
iceSum--;
}
}
}
}
/* 덩어리 탐색 */
int dfs(int row, int col, int curCount) {
// curCount는 덩어리가 차지하는 칸의 개수
visited[row][col] = true;
curCount++;
for (int k=0; k<4; k++) {
int nr = row + dr[k];
int nc = col + dc[k];
if (!outOfRange(nr, nc) && grid[nr][nc]!= 0 && !visited[nr][nc]) {
curCount = dfs(nr, nc, curCount);
}
}
return curCount;
}
void searchIceberg() {
for (int i=0; i<powerN; i++) {
for (int j=0; j<powerN; j++) {
if (grid[i][j] != 0 && !visited[i][j]) {
int count = dfs(i, j, 0);
if (count > maxCount) {
maxCount = count;
}
}
}
}
}
int main() {
// 입력
scanf("%d %d", &N, &Q);
powerN = pow(2, N);
int num;
for (int i=0; i<powerN; i++) {
for (int j=0; j<powerN; j++) {
scanf("%d", &num);
grid[i][j] = num;
if (num != 0) { iceSum += num; }
}
}
for (int i=0; i<Q; i++) {
scanf("%d", &L[i]);
}
// 파이어스톰 시전
for (int i=0; i<Q; i++) {
divideGrid(pow(2, L[i]));
decreaseIce();
}
// 덩어리 탐색
searchIceberg();
// 출력
printf("%d\n%d", iceSum, maxCount);
return 0;
}스터디 (2022-03-06 📚)
✅ 스터디 복기
스터디 직전에 다른 분들 코드를 확인해보는데
다른 분들이 모두 dfs 대신 bfs로 풀어오셔서
bfs로 풀면 뭐가 좋았을까 생각을 해봤다
돌이켜보니 dfs로 풀 때 (dfs로 풀어서라기 보다는 재귀를 활용해서 풀어서)
사실 현재까지 카운트한 얼음 칸의 개수 (curCount 변수) 를 관리해주는 것 때문에
어려운 건 아니지만 잠깐 헤맸었다
dfs 함수 반환형을 정수형으로 해주고
네 방향 다 갈 곳이 없어서 dfs가 끊길 때 curCount 값을 반환해주는 조치가 필요했다
재귀를 안 쓰고 한 함수 안에서 dfs를 스택으로 구현하거나 큐를 활용한 bfs를 사용했으면
curCount 관리가 좀 더 수월했을 것 같다
🙌 스터디를 마무리하며
오늘 부로 교공 알고리즘 스터디가 마무리 되었다
마무리라고 표현하는 게 맞는지 모르겠다 일단락..? 정도로 생각하면 될 것 같다
개발자로 취업하신 우리 과 선배님들께서 시간을 내서
코테 준비하는 재학생들 모아서 만들어주신 스터디였는데
작년 7월부터 벌써 반년이 지났다
정말 많이 배웠고 그만큼 나 자신도 성장한 것 같다
코테가 정말 오르지 못할 너무나도 먼 산처럼 느껴졌는데
이제는 문제 푸는 힘이 조금은 생기지 않았나 싶다
아직도 갈 길은 여전히 멀지만..
다음 주 부터는 나 포함 세명의 재학생끼리 스터디를 이어가기로 했다
한 사람 당 한 문제씩 총 세 문제 골라서 공유하고 풀기로 해서,
오늘 문제 골라보는데 문제 고르는 것도 꽤 어려웠다..
선배님께 또 감사하는 시간이었다..
덕분에 질 좋은 문제들을 풀었던 것 같다 🙏
코로나 때문에 많은 것을 잃은 지난 2년이라고 생각했는데
이처럼 많은 것들을 얻기도 했다
잃었다는 생각에 사로잡혀 얻은 것들을 놓치는 사람이 되지는 말아야겠다 🖤
