2주전에 솔루션 보고 푼.. 사실 솔루션 보고 풀었다고 하기에도 애매한게 거의 답을 베껴쓴 수준이라 완전히 이해해서 푼게 아니라서 일주일의 내가 풀어보기로 했었는데 다른거 하다보니 어느덧 2주나 지나버렸다.
아무튼 다시 풀기로 했었으니 그때 다른 분의 풀이를 봤던걸 완전히 까먹진 않았는지
어느정도는 술술 써내려가긴 했는데 문제는 헷갈렸다는 것..
어차피 결과는 오름차순으로 정렬하고 푸는건 같을테니
0, 0 좌표위치를 내가 제일 편한 위치로 돌려서 생각하기로 했다.
문제는 이거로 인해 더 헷갈리고 결국..
뭔가 잘못 코드를 짰는지 들어가면 안되는 것까지 카운트가 되는 상황이 되어버렸다.. 또르르
결국 다시 원점으로 돌아가서 괜히 헷갈리는 짓 하지말고 평소에 풀던대로 풀자.....라고 생각하고 다시 x와 y 좌표를 변경했는데 그래도 안풀려서 안되겠다 그냥 처음에 했던대로 다시 해보자해서 헷갈리니까 주석을 달기로 하고 다시 작성했다.
처음에 풀기로 했었던 이 상태로 만들어서 풀기로 했다.
그런데 또 같은 결과가 나와써....ㅜㅜ힝구
나는 바보인가 나는 바보인가 나는 바보인가
도대체 왜 1이랑 27이 나오는지 모르겠는걸!
디버깅 해본 결과 1이 출력되는 것은..(vector의 사이즈 값인데)
DFS가 재귀하면서 지혼자 다 돌아가버려서 그렇다는 것을 알게 되었다.
문제의 DFS 코드
사실 문제는 이 코드가 아니였다는 것을 이때까지만 해도 나는 몰랐다.
int DFS(int y, int x){
visited[y][x] = 1;
int count = 1;
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= N || nx >= M ) continue;
if(visited[ny][nx]) continue;
if(arr[ny][nx]) continue;
count += DFS(ny, nx);
}
return count;
}
저렇게 continue라는 벽을 무자비하게 세워놨음에도
왜 arr[ny][nx]가 1이면 continue때문에 DFS가 재귀 호출이 안될텐데 왜 어떻게 뚫고 들어가는건가..? 싶어서 디버깅해보니 DFS에서 arr[ny][nx]가 0으로 출력되는 것을 발견했다.
그래서 continue를 만나지 못하고 재귀호출하면 안되는 부분에서 DFS가 또 터지면서 발생하는 문제라는 것을 알았는데..
문제를 알았음에도 해결하지 못하는 것은 main 함수에서 문제의 arr[ny][nx] 위치를 찍어보면 1로 나온다.. 아니 조금 전까지는 arr[4][0] 위치는 0이라며요........
뭔데ㅜㅜㅜㅜ 무서워ㅠㅠ.......
내 코드는 슈뢰딩거의 코드인가..?
관측하지 않을 땐 0이고 직접 관측하니 1로 나와서 4시간 넘게 고민중인데도 답을 얻지 못하고 있었다.
오기가 생겨서 계속 붙잡고는 있는데 그래도 모르겠다 ㅠㅠ
그리고 나는 진짜 바보였고..
진짜 다 풀어놓고 5시간동안 왜 안되지..? 고민하고 있었는데 입력값 3번 다 받아서 arr 배열을 1로 다 색칠해놓고 나서 DFS 호출을 시켰어야 했는데 다 색칠 하지도 않은 상태에서 DFS 호출시켜서 왜 여기서 0이야..? 이러고 있었다.
이 for문을 저 안에서 돌리고 있으니 당연히 안되지..............ㅋㅋㅋㅋㅋㅋㅋㅋㅋ
아무튼 풀었다..... 7시까지 해보고 안되면 c++ 알고리즘 장인 선생님께 질문하러 가야겠다했는데 풀었다...... 풀었는데도 뭔가 억울해 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
정말 질문했으면 어? 내가 왜 이걸 이렇게 풀었지..? 하고 부끄러울 뻔 했다.
아 진짜 금방 풀수 있었는데 5시간 날려서 너무 시간이 아깝지만 ㅋㅋㅋㅋㅋㅋㅋ
한편으로는 끝까지 문제 풀었다는게 너무 후련하다..
다음부턴 입력 받는거 확인하고 또 확인해야지.
풀이 코드
#include <bits/stdc++.h>
using namespace std;
#define y1 aaaa
int M, N, K;
int visited[105][105];
int arr[105][105];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int x1, y1, x2, y2;
vector<int> ret;
int DFS(int y, int x){
visited[y][x] = 1;
int count = 1;
for(int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if(ny < 0 || nx < 0 || ny >= N || nx >= M ) continue;
if(visited[ny][nx]) continue;
if(arr[ny][nx]) continue;
count += DFS(ny, nx);
}
return count;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> M >> N >> K; // N = 세로, M =가로
for(int i = 0; i < K; i++){
cin >> y1 >> x1 >> y2 >> x2;
for(int y = y1; y < y2; y++){
for(int x = x1; x < x2; x++){
arr[y][x] = 1;
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(arr[i][j] || visited[i][j]) continue;
ret.push_back(DFS(i, j));
}
}
sort(ret.begin(), ret.end());
cout << ret.size() << "\n";
for(int i : ret){
cout << i << " ";
}
}과거의 내가 지금의 나한테 풀라고 토스한 문제를 어쨌든 우여곡절끝에 풀긴해서 정말 다행이다.
코드 작성할 때 꼼꼼하게 보는 습관이 정말 중요하다는 것을 다시 깨닫는 순간이었다.
이 짤에 아래있는 사람처럼 포기하고 돌아서는 사람이 될 뻔 했다.ㅋㅋㅋ
정말 그냥 개념조차 아예 몰라서 손도 못대는거 아닌이상은 앞으로도 삽질 오래 하더라도 오기로 풀어봐야겠다.
