반응형 [백준]214 [BaekJoon/백준] 2638번 치즈 어제부로, 모든 골드 4문제를 끝냈고 덕분에 골드2로 승격했다. 오늘 문제는, 조금 더 쉽게 풀 수 있었는데 그렇지 못한 문제였다. 나는 모눈종이의 맨 가장자리(가생이)들을 모두 dfs를 돌아주며 치즈의 바깥쪽과 안쪽을 구분해주려했는데, 문제에 이런 내용이 있었다 즉, dfs(0,0) 한번만 해서 체크해주면 치즈 바깥쪽과 안쪽을 구분하기에 충분하다는 것이다. 이것만 빼면 다른 분들의 풀이와 비슷하다. 1. 먼저 치즈의 바깥쪽을 구분해주기 위해, dfs를 돌면서 해당 부분을 -1로 체크해준다. 2. 전체를 for문을 돌며, 현재 칸이 치즈(=1)인 경우 상하좌우 중에 -1인 곳이 두 개 이상 있으면 치즈를 없애버린다(=0) 반복 /* 가생이 한바퀴를 각각 dfs처리해주면 외부와 내부를 분리하는데 충분할듯... 2022. 7. 31. [BaekJoon/백준] 15683번 감시 아무쪼록 내가 제 시간에 풀 수 있는 문제는 절대 아니였다. 풀이를 찾아봤는데도, 해석하여 푸는데도 오래걸렸고, 반례를 찾아내는데에도 오래걸렸다. 요 근래 문제를 풀면서 가장 오랜 시간을 사용했다. 문제에는 백트래킹 개념을 사용했다. 이 때, 내 풀이에 있어서 문제에서 주의할 점은 각 카메라가 감시하는 영역을 모두 동일한 값으로 해주면 예를들어 첫번째 카메라가 9라는 숫자로 감시영역 표시를 해줬는데 세번째 카메라가 dfs를 돌다가, 감시 해제를 통해 토글을 했는데 해당 부분이 이미 첫번쨰 카메라가 감시하는 부분을 지워버릴 수 있다. 따라서 방법은 두 가지가 있다. 1. 아래와 같은 방식을 사용하면서, VISIT[i] = true; dfs(); VISIT[i] = false; 각 카메라(x번째 카메라)가 .. 2022. 7. 30. [BaekJoon/백준] 1062번 가르침 이런 문제 너무 좋다. 비트 마스킹 관련 문제인데, 다른 분들의 풀이를 보고 풀었다. 그 중에서도, 내가 정말 원하는 방향으로 푸신 분이 있어서 해당 글을 많이 참고했다!!! 참고로 1 = b)? a: b) using namespace std; int ALPHABET; int WORDS[50]; // N개(최대50개)의 단어에서, 쓰인 알파벳들을 비트마스킹하여 저장하는 역할. int N, K; int TOTAL_MAX = 0; void dfs(int start, int cnt) { if(cnt == K) { int T = 0; for(int i = 0; i < N; i++) { if((WORDS[i] & ALPHABET) == WORDS[i]) T++; } TOTAL_MAX = MAX(T, TOTAL_M.. 2022. 7. 29. [BaekJoon/백준] 14442번 벽 부수고 이동하기 2 이번 문제는 2206번 벽 부수고 이동하기 문제와, 14923번 미로 탈출 문제와 같은 유형의 문제다. 다만 위 문제들은, 벽을 최대 한 번 부술 수 있다는 점인데 이번 문제는 벽을 K번 부술 수 있다는 점이 다르다. 14923번을 풀 때에는, VISIT을 bool로 두고 추가로 DEPTH를 두어 최단거리를 계산했는데, 그럴 필요 없이 VISIT을 int로 두어 0은 미방문, 그 외에는 최단거리 값으로 생각하여 계산하면 된다. 하나의 배열로 DEPTH와 VISIT 처리를 할 수 있다는 것이다. 또한 2206번을 풀 때에는 불필요하게 MAX를 사용하거나 if문을 비교적 리팩토링 하지 못하고 중복적이게 작성한 것 같은데, 이번에는 좀 더 깔끔하게 작성하여 푼 것 같다. 두 문제를 통해 더 잘 풀게 된 것 같.. 2022. 7. 28. 이전 1 2 3 4 5 6 7 8 ··· 54 다음 반응형
