📌 참고
교공 알고리즘 스터디에서 다룬 문제는 19주차부터 벨로그에 기록하고 있습니다 (18주차 이전 문제들을 추후 복습 겸 업로드할 계획도 있습니다 🤗) 그 외 개인적으로 풀어본 백준 및 프로그래머스 문제는 스스로 유의미하다고 여겨진 부분들이 있는 문제만 선별하여 벨로그에 기록하고 있습니다 벨로그에 올라오지 않은 다른 문제와 코드가 궁금하신 분들은 아래의 github에서 추가로 확인하실 수 있습니다 👀 방문해주셔서 감사합니다 🙏
💚 github | dianstar/Algorithm-BOJ
💚 github | dianestar/Algorithm-Programmers
교공 알고리즘 스터디 20주차 삼성기출
문제풀이 (2022-01-16 SUN 💻)
🤔 사담
개인적으로 지난 주에 풀었던 청소년 상어 문제보다 티어가 낮은데도 불구하고
처음에 어떻게 풀어야할지 떠올리는게 난해했다 (?)
어제 막 계절학기 종강해서 공부하기 싫어서 그런 것일 수도... 머쓱
와중에 생각해보니까 DFS 문제는 많이 풀었는데 BFS 문제는 생각보다 많이 안 풀어본듯 싶다..
⭐ 풀이의 핵심
👉 BFS로 상어로부터 먹을 수 있는 물고기들까지의 거리들을 싹 계산하고 시작
거리 값, 행렬, 인덱스 값를 담는 Fish 구조체 를 선언해서 탐색한 사람들도 있는데,
나는 거리를 담는 dist 행렬만 따로 만들어서 풀었다-
- 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
- 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
👉 더불어 이 조건들에 대해
cmp 구조체 선언 + priority_queue 에다가 먹을 수 있는 후보 물고기들을 담아서
탐색 종료 후 해당 큐의 front에 있는 물고기를 먹으러 가도록 푼 사람들도 있었는데,
나는 탐색 종료 후 dist 행렬 최상단+최좌측부터 살피며 최솟값 업데이트를 해주는 식으로 짰다-
🚨 간과 또는 실수한 부분
거리의 최댓값(20x20=400)을 행렬 인덱스의 최댓값이랑 똑같이 20이라고 define하는..
말도 안되는 오류를 저지르는 바람에 테스트케이스 다 통과하고도 틀렸습니다 목격..
진짜 로직이나 뼈대 말고 이런 말도 안되는 부분에서 실수해버리면 절대 못 찾는 것 같다
🔽 스터디 전 제출 코드 (C++)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX_INDEX 20
#define MAX_DIST 400
struct Shark {
int row, column, num, size;
};
Shark shark;
int N;
int matrix[20][20];
int dist[20][20];
int time = 0;
// 위쪽 왼쪽 아래쪽 오른쪽
int moveRow[4] = {-1, 0, 1, 0};
int moveCol[4] = {0, -1, 0, 1};
void solution() {
queue<pair<int, int>> distChecker;
while (1) {
//dist 행렬 초기화
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
dist[i][j] = -1;
}
}
dist[shark.row][shark.column] = 0;
/* check distance (bfs) */
distChecker.push({shark.row, shark.column});
while (!distChecker.empty()) {
pair<int, int> curr = distChecker.front();
distChecker.pop();
for (int i=0; i<4; i++) {
int nextRow = curr.first + moveRow[i];
int nextCol = curr.second + moveCol[i];
// cf) 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
// nextRow 또는 nextCol 값이 matrix 범위 밖으로 벗어나거나 matrix[nextRow][nextCol]이 지나갈 수 없는 칸이거나 이미 거리 값을 체크한 칸일 경우 스킵
if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N
|| matrix[nextRow][nextCol] > shark.size || dist[nextRow][nextCol] != -1) {
continue;
}
// 거리 값 체크 및 해당 좌표 bfs queue에 push
dist[nextRow][nextCol] = dist[curr.first][curr.second] + 1;
distChecker.push({nextRow, nextCol});
}
}
/* choose target */
//minDist, minRow, minCol 값 초기화
int minDist = MAX_DIST;
int minRow = MAX_INDEX;
int minCol = MAX_INDEX;
// cf) 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.
// cf) 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
if (matrix[i][j] < shark.size && matrix[i][j] != 0 && dist[i][j] != -1 && dist[i][j] < minDist) {
minDist = dist[i][j];
minRow = i;
minCol = j;
}
}
}
if (minDist == MAX_DIST) { // 더 이상 먹을 수 있는 물고기가 공간에 없다면 종료
break;
}
/* eat fish */
// cf) 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
shark.row = minRow;
shark.column = minCol;
shark.num++;
matrix[minRow][minCol] = 0;
// cf) 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
if (shark.num == shark.size) {
shark.num = 0;
shark.size++;
}
time += minDist;
}
}
int main() {
scanf("%d", &N);
int status;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
scanf("%d", &status);
matrix[i][j] = status;
if (status == 9) {
matrix[i][j] = 0;
shark.row = i;
shark.column = j;
shark.num = 0;
shark.size = 2;
}
}
}
solution();
printf("%d", time);
return 0;
}스터디 (2022-01-24 SUN 📚)
✅ 스터디에서 얻은 Tip
먹을 수 있는 모든 물고기에 대해 탐색 ❌
bfs queue의 현재 사이즈만큼의 횟수만 탐색해본 후 먹을 수 있는 물고기가 있는지 확인 시
같은 최소 거리에 있는 물고기들에 대해서만 탐색 하고 멈출 수 있어서 효율성이 높아진다!
🔽 스터디 후 수정해본 코드 (C++)
/* 스터디에서 얻은 Tip을 반영하여 수정해본 코드 */
// 먹을 수 있는 "모든" 물고기에 대해 탐색 X
// "bfs queue의 현재 사이즈만큼의 횟수만" 탐색해본 후 먹을 수 있는 물고기가 있는지 확인 시
// <같은 최소 거리에 있는 물고기들에 대해서만 탐색> 하고 멈출 수 있어서 효율성이 높아진다
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX_INDEX 20
#define MAX_DIST 400
struct Shark {
int row, column, num, size;
};
Shark shark;
int N;
int matrix[20][20];
int dist[20][20];
int time = 0;
// 위쪽 왼쪽 아래쪽 오른쪽
int moveRow[4] = {-1, 0, 1, 0};
int moveCol[4] = {0, -1, 0, 1};
bool cmp(const pair<int, int> &a, const pair<int, int> &b) {
if (a.first == b.first) {
return a.second < b.second;
}
return a.first < b.first;
}
void solution() {
while (1) {
// minDist, minRow, minCol 값 초기화
int minRow = MAX_INDEX;
int minCol = MAX_INDEX;
int minDist = MAX_DIST;
// dist 행렬 초기화 후 현재 shark 위치의 dist 행렬 값 0으로 설정
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
dist[i][j] = -1;
}
}
dist[shark.row][shark.column] = 0;
// bfs queue 초기화 후 큐에 현재 shark 위치 push
queue<pair<int, int>> distChecker;
distChecker.push({shark.row, shark.column});
// bfs
while (!distChecker.empty()) {
vector<pair<int, int>> minCandidates;
int queueSize = distChecker.size();
for (int i=0; i<queueSize; i++) { // queueSize 변수 및 해당 for문을 추가한 것이 수정의 핵심
pair<int, int> curr = distChecker.front();
distChecker.pop();
for (int i=0; i<4; i++) {
int nextRow = curr.first + moveRow[i];
int nextCol = curr.second + moveCol[i];
// cf) 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.
// nextRow 또는 nextCol 값이 matrix 범위 밖으로 벗어나거나 matrix[nextRow][nextCol]이 지나갈 수 없는 칸이거나 이미 거리 값을 체크한 칸일 경우 스킵
// dist[nextRow][nextCol] !=1 조건식으로 bfs visited 여부 체크
if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= N
|| matrix[nextRow][nextCol] > shark.size || dist[nextRow][nextCol] != -1) {
continue;
}
// 지나갈 수 있거나 먹을 수 있는 칸에 대해 거리 값 체크 및 해당 좌표 bfs queue에 push
dist[nextRow][nextCol] = dist[curr.first][curr.second] + 1;
distChecker.push({nextRow, nextCol});
// 먹을 수 있는 물고기를 minCandidates에 push
if (matrix[nextRow][nextCol] != 0 && matrix[nextRow][nextCol] < shark.size) {
minCandidates.push_back({nextRow, nextCol});
}
}
}
// minCandidates가 존재할 경우 타겟 선정
if (minCandidates.size() != 0) {
if (minCandidates.size() != 1) { // cf) 거리가 가까운 물고기가 많다면,
sort(minCandidates.begin(), minCandidates.end(), cmp); // 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다. (cmp 함수로 구현)
}
minRow = minCandidates[0].first;
minCol = minCandidates[0].second;
minDist = dist[minRow][minCol];
break;
}
}
if (minDist == MAX_DIST) { // 더 이상 먹을 수 있는 물고기가 공간에 없다면 종료
break;
}
// 물고기를 먹는 부분
// cf) 이동과 동시에 물고기를 먹는다. 물고기를 먹으면, 그 칸은 빈 칸이 된다.
shark.row = minRow;
shark.column = minCol;
shark.num++;
matrix[minRow][minCol] = 0;
// cf) 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다.
if (shark.num == shark.size) {
shark.num = 0;
shark.size++;
}
// 시간 업데이트
time += minDist;
}
}
int main() {
scanf("%d", &N);
int status;
for (int i=0; i<N; i++) {
for (int j=0; j<N; j++) {
scanf("%d", &status);
matrix[i][j] = status;
if (status == 9) {
matrix[i][j] = 0;
shark.row = i;
shark.column = j;
shark.num = 0;
shark.size = 2;
}
}
}
solution();
printf("%d", time);
return 0;
}
벨로그에는 주로 알고리즘 문제를 풀고 기록합니다 ✍