[BaekJoon/백준] 2636번 치즈
그렇게 깔끔하게 풀진 못해서 조금 아쉽다. 그리고 나는 DFS를 썼는데, 다른분들의 코드를 보니 BFS로 푸는 방법이 더 효율적일 것 같다. SIDE 부분을 Queue에 넣어준 뒤, 그것들의 인접정보를 이용해서 점점 줄여나가는.. BFS 문제. #include #include using namespace std; int N, M; int ARR[100][100]; bool VISIT[100][100]; int SIDE = 2; int mx[4] = {-1, 1, 0, 0}; int my[4] = {0, 0, -1, 1}; int FLIP_COUNT; int BACKUP; void dfs(int x, int y) { int xx, yy; VISIT[x][y] = true; if(ARR[x][y] == 1)..
2022. 6. 24.
[BaekJoon/백준] 2583번 영역 구하기
19시에 자버렸고,, 22:30분에 눈을 떴다.. 생활패턴 망했네. 이 문제를 풀 땐, x축 기준으로 뒤집어서 배열 상으로 생각하여 풀었다. 시간복잡도는 dfs => O(n) x n^2 = O(n^3) 정도 나오는데, 사실 이정도는 안나올 것 같다. #include #include #include using namespace std; int Arr[100][100]; int N, M, K; int mx[4] = {-1, 1, 0, 0}; int my[4] = {0, 0, -1, 1}; int COUNT; vector T; int T_SIZE; void dfs(int x, int y) { Arr[x][y] = 1; COUNT++; int xx, yy; for(int i = 0; i < 4; i++) { x..
2022. 6. 24.
[BaekJoon/백준] 11048번 이동하기
DP로 문제를 해결했다. DFS, BFS로 풀 수 있는 문제가 아니다. 1000 x 999 x 998 ... 엄청난 시간이 나올 것. // 오른쪽, 아래, 오른쪽아래 움직일 수 있는 특성. // 행 기준으로 '->' 순환하며 dp 하면 될 것 같다. // 시간복잡도 O(n) #include #define MAX(a,b) (a>=b?a:b) using namespace std; int N, M; int Arr[1000][1000]; int DP[1000][1000]; int sx[3] = {0, -1, -1}; int sy[3] = {-1, 0, -1}; int tmp_x, tmp_y; int main() { cin >> N >> M; for(int i = 0; i < N; i++) { for(int j ..
2022. 6. 23.