주말에 숭고한 알고리즘 콘테스트에 나갔다.
나는 작년 6월부터 알고리즘 공부를 하기 시작했는데, 처음으로 나가보는 대회였다. 걱정도 많이하고 기대도 많이 하면서 4시간 동안 문제를 풀었는데....
하.......
초반에 진짜 페이스 좋고 빠르게 풀어나가다가 중반부터 아예 막혔다.
아무리 생각해도 푸는 아이디어가 맞는 거 같은데 계속 WA를 받았다.
결국 개같이 멸망.
그래도 처음 나가보는거니까 나가는 거에 의의를 두고 여느 때처럼 오늘 문제를 풀었는데 이 문제도 푸는 아이디어가 맞는 거 같은데 계속 WA를 받아 답을 보았다...
결국 기존에 생각한 아이디어랑 다르게 푼 사람의 코드를 참고하고 제출했는데 나와 같은 생각을 하신 분들의 코드도 있어서 더욱 생각이 깊어졋다...
내가 알고리즘 공부를 하면서 가장 많이 참고한 두 분이 있는데 얍문, 꾸준함 님이다...
아무리 생각해도 모르는 문제를 구글에 쳐보면 항상 윗 부분에 뜨시는 분들이다 ㅋㅋㅋㅋ 그 두 분은 내가 생각한 아이디어를 맞게 구현하셨고 통과하셨다...
근데 나는 왜...?!?!?!? 후.... 더 노력해야겠지 뭐...ㅠㅠ
암튼 서론이 매우 길었다.. 문제 리뷰 드가자...
문제링크
https://www.acmicpc.net/problem/2636
설명
치즈가 모두 녹을 때까지 걸리는 시간과 다 녹기 전 마지막 치즈의 개수를 구하는 문제이다.
치즈가 0과 접한다고 모두 녹는 것이 아니다.
외곽에 존재하는 0과 접한 0들이 치즈를 녹일 수 있다.
만약 0이 치즈로 둘러싸여있다면 그 0은 치즈를 녹일 수 없다.
그래서 내가 처음 생각한 알고리즘은 다음과 같다.
- 외곽의 0과 접한 0들을 모두 3으로 만든다. (bfs)
- 3과 접한 치즈는 녹을 치즈이므로 2로 만든다. (bfs)
- 녹을 치즈(2)를 0으로 바꾸어주고 다시 1의 과정부터 반복한다.
이 과정에서 치즈의 개수가 0이 될 때, 반복문을 탈출하고 시간과 직전의 개수를 출력한다.
하지만 아침에는 계속 TLE와 WA를 받았고, 점심 먹고 돌아와서 코드를 싹 다 지운 뒤 다시 짜고 제출했는데도 TLE를 받아서 빠르게(?) 포기했다.
다른 사람들의 풀이를 보고 고친 알고리즘은 다음과 같다.
-
외곽 0에서부터 bfs를 실행한다.
-
큐가 빌 때까지 아래의 과정을 반복한다.
1) 0을 만난다면 큐에 넣어주고 마저 탐색한다.
2) 1을 만난다면 녹는 치즈이므로 0으로 바꿔준다.
이 때, 모두 방문체크를 해준다.
-
치즈가 모두 녹을 때까지 1, 2의 과정을 반복한다.
내가 맨 처음 생각한 알고리즘과의 차이점은 중간에 녹을 치즈를 설정하는 과정을 생략하는 부분이다.
잘 생각해보면, 위 알고리즘에서 녹을 치즈를 2로 설정한 다음, 바로 0으로 바꾸어준다.
어차피 바로 0으로 바꾸어 줄 거라면, 1을 만나자마자 0으로 바꾸어 준 다음 큐에 넣지 않으면 된다.
큐에 넣지 않는다면 그 점과 인접한 점은 탐색하지 않는다.
내부에 있던 치즈는 자연스럽게 다음 bfs 때 처리하게 된다는 것이다.
고친 알고리즘은 아이디어도 훨씬 간결하고 코드도 짧다.
하지만 사람은 누구나 먼저 생각한 아이디어에 미련이 남기 마련이다.
아마 나는 저 복잡한(?) 아이디어를 구현하는 긴 코드 중 어느 한 줄 이상이 말썽을 피우는 게 아닐까 짐작하고 있다.
아마 숭고한 알고리즘 대회에서 계속 틀렸습니다를 받은 이유도 이거겠지....
얍문님과 꾸준함님의 코드를 보고 내 아이디어로도 충분히 풀 수 있는 문제라는 걸 깨닫고 고민이 늘었다... 솔직히 말하자면 오늘은 절대 못 풀 거 같다 ㅋㅋㅋㅋㅋ
이미 멘탈 털털 털렸다....
그래도 더 복잡한 아이디어라도 구현해서 풀어봐야 한다는 생각은 든다.
코테를 보게 된다면 시간제한도 있을 것이고 아무래도 맨 처음 생각한 아이디어로 문제를 풀려고 노력할 것이다...
처음 생각한 아이디어가 간결하면 좋겠지만 조금은 복잡하다면 천천히 그리고 꼼꼼하게 그 아이디어를 구현할 수 있는 능력도 필요하다는 생각이 이번 대회를 통해 들었다.
간결한 아이디어는 다양한 문제를 접하면서 내 것으로 만든다면 충분히 얻을 수 있는 능력이라 생각한다.
복잡한 아이디어를 구현하는 능력은 초심으로 돌아가야 할 거 같다.
알고리즘 공부를 하던 초기에는 그 문제를 풀 때까지 절대 정답도 보지 않고 계속 시도했었다. 보통 잘못 걸리면 3시간 이상은 기본으로 걸렸던 거 같다.
요새는 1시간 이상은 시간낭비라고 생각하기도 하고 쉽게 포기하는 습관이 생긴 거 같기도 하다...
조금 더 초심으로 돌아가서 공부해야겠다.... 물론 딴 공부도....
코드
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct node {
int y, x;
};
int n, m, map[101][101];
int visited[101][101], dir[4][2] = { {-1, 0},{0,1},{1,0},{0,-1} };
void input()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> map[i][j];
}
void setair() // 시간마다 map에서 녹는 치즈 변경 -> 이게 가능한 이유 : 0과 인접한 치즈만 변경해주므로 안쪽 치즈나 구멍도 고려해주기 가능
{
queue<node> q;
q.push({ 1,1 });
visited[1][1] = 1;
while (!q.empty())
{
int y = q.front().y;
int x = q.front().x;
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dir[i][0];
int nx = x + dir[i][1];
if (ny <= 0 || ny > n || nx <= 0 || nx > m || visited[ny][nx] == 1) // 범위에 벗어나거나 이미 방문한 곳이라면 pass
continue;
if (map[ny][nx] == 0)
q.push({ ny, nx });
else // 0과 인접한 치즈라면 0으로 바꿔줌
map[ny][nx] = 0;
visited[ny][nx] = 1;
}
}
}
void solution()
{
int time = 0, cnt, mcnt = 0;
while (1)
{
cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (map[i][j] == 1)
cnt++;
setair();
if (cnt > 0) // 치즈가 하나라도 존재한다면
{
time++;
mcnt = cnt;
}
else
break;
memset(visited, 0, sizeof(visited));
}
cout << time << '\n' << mcnt;
}
void solve()
{
input();
solution();
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}