[백준 BOJ] 2573번 - 빙산 (C++)
📌 참고
교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏
💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers
교공 알고리즘 스터디 22주차 탐색문제
문제풀이 (2022-02-09 WED 💻)
🤔 사담
테케가 하나여서 불안했던 것 빼고는 (?) 무난하게 잘 풀었던 문제였다
인풋 크기도 크지 않아서 여유롭게 푼 것 같다
⭐ 풀이의 핵심
빙산이 분리되는 것을 어떻게 파악할 것인가만 잘 떠올리면 쉬운 문제이다
- 현재 전체 N*M 칸에서 0이 아닌 칸의 개수 (아래 코드에서 iceCount 변수)
- 임의의 0이 아닌 칸 하나로부터 한 번 dfs 또는 bfs 탐색을 돌면서 카운트한 0이 아닌 칸의 개수 (아래 코드에서 curCount 변수)
위의 두 변수를 비교하여 값이 다르면 덩어리가 2개 이상으로 분리되었다고 생각할 수 있다
🚨 간과 또는 실수한 부분
빙산의 높이를 감소시키는 함수 (아래 코드에서 decrease 함수) 에서
처음에는 이중 for문을 돌며 매 칸마다 바로바로 빙산 높이를 감소시키고
감소시킨 값을 입력받은 원본 2차원 배열 (아래 코드에서 sea 벡터) 에 반영했다
🤦♀️ 이렇게 구현하면 앞서 탐색한 칸의 높이가 감소해서 0이 되었을 경우
이후 탐색하는 칸에서 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수
(아래 코드에서 zeroCount 변수) 가 달라져서 결과가 다르게 나올 수 있다
👉 따라서 nextSea라는 벡터를 따로 선언 해줘서
원본 sea 벡터에 영향을 주지 않은 채 이중 for문을 돌며 nextSea 벡터를 채운 후
마지막에 decrease 함수의 반환 값으로 해당 nextSea 벡터를 반환하여
sea 벡터를 한 번에 갱신하는 방법으로 구현해주었다
🔽 코드 (C++)
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> sea(300, vector<int>(300));
vector<vector<bool>> visited(300, vector<bool>(300));
int iceCount; // 현재 sea 벡터에서 0이 아닌 값이 저장된 칸의 개수
int curCount; // search 함수로 탐색한 한 덩어리 속 0이 아닌 값이 저장된 칸의 개수
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
vector<vector<int>> decrease() {
vector<vector<int>> nextSea(300, vector<int>(300, 0));
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (sea[i][j] != 0) {
int zeroCount = 0; // 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수
for (int k=0; k<4; k++) {
if (sea[i+dr[k]][j+dc[k]] == 0) {
zeroCount++;
}
}
// cf) 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다.
nextSea[i][j] = sea[i][j] - zeroCount;
if (nextSea[i][j] <= 0) {
// cf) 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다.
nextSea[i][j] = 0;
iceCount--;
}
}
}
}
return nextSea;
}
void initialize() {
// visited 벡터와 curCount 변수 초기화
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
visited[i][j] = false;
}
}
curCount = 0;
}
void search(int i, int j) {
// dfs
visited[i][j] = true;
curCount++;
for (int k=0; k<4; k++) {
int nextRow = i+dr[k];
int nextCol = j+dc[k];
if (sea[nextRow][nextCol] != 0 && !visited[nextRow][nextCol]) {
search(nextRow, nextCol);
}
}
}
int main() {
scanf("%d %d", &N, &M);
int num;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
scanf("%d", &num);
sea[i][j] = num;
if (num != 0) {
iceCount++;
}
}
}
int year = 0;
while (1) {
// cf) 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
if (iceCount == 0) {
printf("0");
break;
}
bool endFlag = false;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (sea[i][j] != 0) { // 0이 아닌 값이 저장된 임의의 칸 지정
initialize(); // 새로운 연도의 빙산 상태 탐색을 위해 초기화
search(i, j); // 해당 칸이 포함된 한 덩어리의 0이 아닌 칸의 개수 탐색
endFlag = true;
break;
}
}
if (endFlag) {
break;
}
}
if (curCount != iceCount) { // 빙산이 두 덩어리 이상으로 분리된 경우
printf("%d", year);
break;
}
sea = decrease(); // 빙산의 높이 감소
year++;
}
return 0;
}
스터디 (2022-02-14 SUN 📚)
🤔 사담
내 코드에 대해 발표하는..? 말하는 연습을 좀 해야될 것 같다..
뭔가 구현은 잘 해가도 설명을 못해서
스터디원들이 내 코드를 이해하기 어려워하는 경우가 종종 있는 것 같다....
벨로그를 열심히 쓰다보면 도움이 되겠지? 😥
✅ 스터디 복기
-
dfs 또는 bfs로 전체 행렬을 다 돌며 빙산의 덩어리 개수를 구하고 덩어리 개수가 2개 미만인지 이상인지 체크하는 방법 으로 구현하신 분들이 많았다
👉 효율성 면으로 따져봤을 때는 내가 구현한 방식이 더 좋아보였다
-
나를 제외한 모든 스터디원 분들이 탐색할 때 행렬 인덱스가이 0보다 작거나 N,M보다 같거나 클 경우에 대해 범위 체크해주는 함수를 포함해서 코드를 짜오셨다
배열의 첫 번째 행과 열, 마지막 행과 열에는 항상 0으로 채워진다.
👉 사실상 이 문제는 입력 조건에 위와 같은 조건이 있기 때문에 해당 부분을 생략해줘도 무방 하다
(같은 맥락으로 덩어리 탐색할 때도 첫 번째 행과 열, 마지막 행과 열은 빼고 탐색해도 되는 것이었는데 이 부분은 또 0번 인덱스부터 끝 인덱스까지 다 탐색하는 for문으로 짰었다 띠용)
-
추상화 수준을 맞춰서 코드를 리팩토링 해준다면 코드의 가독성이 더 좋아질 것 같다는 피드백을 받았다
i) 빙산이 두 덩어리로 분리되었는지 체크
ii) 빙산의 높이 감소👉 이 문제는 사실상 이렇게 크게 두 가지 부분으로 나뉘는데 내 코드는 main함수에서
ii) 부분에 대해서는 함수 호출 한 줄로 깔끔하게 끝나지만
i) 부분에 대해서는 꽤나 디테일하게 추가적인 처리를 해주는 부분이 드러나있어서
받은 피드백이었다 i) 부분에 대해서 한 번 더 함수로 감싸주면 좋을 것 같다는 피드백이었다
🔽 스터디 후 수정해본 코드 (C++)
구현 원리 측면에서 크게 다를 건 없지만
복기 내용을 기반으로 사소하게 나마 코드를 수정해보았다
#include <iostream>
#include <vector>
using namespace std;
int N, M;
vector<vector<int>> sea(300, vector<int>(300));
vector<vector<bool>> visited(300, vector<bool>(300));
int iceCount; // 현재 sea 벡터에서 0이 아닌 값이 저장된 칸의 개수
int curCount; // search 함수로 탐색한 한 덩어리 속 0이 아닌 값이 저장된 칸의 개수
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
vector<vector<int>> decrease() {
vector<vector<int>> nextSea(300, vector<int>(300, 0));
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
if (sea[i][j] != 0) {
int zeroCount = 0; // 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수
for (int k=0; k<4; k++) {
if (sea[i+dr[k]][j+dc[k]] == 0) {
zeroCount++;
}
}
// cf) 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다.
nextSea[i][j] = sea[i][j] - zeroCount;
if (nextSea[i][j] <= 0) {
// cf) 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다.
nextSea[i][j] = 0;
iceCount--;
}
}
}
}
return nextSea;
}
void initialize() {
// visited 벡터와 curCount 변수 초기화
for (int i=1; i<N-1; i++) {
for (int j=1; j<M-1; j++) {
visited[i][j] = false;
}
}
curCount = 0;
}
void search(int i, int j) {
// dfs
visited[i][j] = true;
curCount++;
for (int k=0; k<4; k++) {
int nextRow = i+dr[k];
int nextCol = j+dc[k];
if (sea[nextRow][nextCol] != 0 && !visited[nextRow][nextCol]) {
search(nextRow, nextCol);
}
}
}
bool checkSplit() {
bool endFlag = false;
for (int i=1; i<N-1; i++) {
for (int j=1; j<M-1; j++) {
if (sea[i][j] != 0) { // 0이 아닌 값이 저장된 임의의 칸 지정
initialize(); // 새로운 연도의 빙산 상태 탐색을 위해 초기화
search(i, j); // 해당 칸이 포함된 한 덩어리의 0이 아닌 칸의 개수 탐색
endFlag = true;
break;
}
}
if (endFlag) {
break;
}
}
if (curCount != iceCount) { // 빙산이 두 덩어리 이상으로 분리된 경우
return true;
}
else { // 빙산이 여전히 한 덩어리인 경우
return false;
}
}
int main() {
scanf("%d %d", &N, &M);
int num;
for (int i=0; i<N; i++) {
for (int j=0; j<M; j++) {
scanf("%d", &num);
sea[i][j] = num;
if (num != 0) {
iceCount++;
}
}
}
int year = 0;
while (1) {
// cf) 만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다.
if (iceCount == 0) {
printf("0");
break;
}
if (checkSplit()) {
printf("%d", year); // 빙산이 두 덩어리 이상으로 분리되었는지 확인
break;
}
sea = decrease(); // 빙산의 높이 감소
year++;
}
return 0;
}
Author And Source
이 문제에 관하여([백준 BOJ] 2573번 - 빙산 (C++)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dianestar/백준BOJ-2573번-빙산저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)