알고리즘 /BFS + DFS (6) 썸네일형 리스트형 [백준] BFS로 토마토 문제들을 푸는 법: queue 이용하기 한 번 더 풀어본 토마토 문제! 이번에는 queue를 사용했다. 하루에 한 칸씩 이동해야 하므로, qsize = q.size로 하룻동안 이동할 양을 고정시켜두면 중간에 q에 새로운 값이 들어오더라도 상관없다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include #include using namespace std; int M, N; int box[1000][1000]; bool visited[1000][1000]; int ans = 0; queue q.. [SW Expert Academy] 미생물 격리_2382 군집 내에 방향, 위치, 크기같은 정보들이 필요했기 때문에 구조체를 사용했다. 이미 군집이 있던 위치로 간 경우, 군집들의 크기를 서로 비교하기 위해서 maxSize라는 변수를 사용했다. 자신의 군집의 크기가 가장 큰 경우, 방향과 maxSize를 자신의 방향과 사이즈로 바꾼다. (num은 합쳐진 군집들의 크기고 maxSize는 군집들 여러개중에 가장 큰 군집의 크기이다.) * 실수했던 것 * isOut 체크를 군집의 크기를 나타내는 N이 아니라 n으로 검사했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4.. [백준] 이분 그래프_1707 사실 이 문제는 스스로 풀지는 못했다. 결국 인터넷을 참고했다. 처음엔 set1, set2라는 벡터를 만들어서 dfs의 연결을 따라가면서 연결이 될 때마다 각각 다른 set에 넣고, 중복돼서 들어갔는지를 확인해야 하나? 하고 생각했는데 전혀 아니었고... int colored[20001] 이라는 리스트를 만들어서 -1, 1이 각각 다른 색깔, 0은 색이 칠해지지 않은 노드라고 생각하고 풀면 되는 문제였다. 노드들을 집합으로 나눌 때는 따로 리스트를 만들어서 각각의 색들을 서로 다른 정수로 표현해서 저장하면 되는구나. 노드들을 다 색칠한 다음에는 인접리스트의 각 노드들을 탐색하면서 이에 연결되어 있는 노드들이 같은 집합인지 아닌지를 확인하면 된다. * 부족했던 점 * 1. 인접 리스트와 인접 행렬의 개념을.. [백준] 빙산_2573 이 문제는 bfs와 dfs 둘 다 써서 풀어보았다. 빙산을 녹이는 부분은 bfs로, 2개 이상으로 나뉘었는지 확인하는 부분은 dfs로 풀었다. 2개 이상이 되면 반복문을 깨도록 하였고, 2개 이상이 되었는지 확인하는 중에 빙산이 하나라도 남아있으면 remain 값을 true로 만들었다. 반복문이 모두 끝난 뒤까지 remain 값이 false로 남아있으면 year = 0 이 부분이 실행되도록 하였다. 처음에는 일년동안 빙산을 녹이고 그 다음 빙산을 녹일때 그 전에 다 녹아버린 빙산이 영향을 주면 안되는데, 이걸 어떻게 구현해야 할지 몰라서 헷갈렸는데, 같은 크기의 배열을 하나 더 만들어두면 해결되는 문제였다. * 실수했던 것 * 1. 풀다가 문제를 착각해서 입력은 m, n으로 받아놓고 반복문을 쓸때 for.. [백준] 단지번호 붙이기_2667 처음으로 혼자서 제대로 풀어본 dfs 문제...! * 실수했던 것 * 1. 입력 7 0110100 0110101 1110101 ... 입력이 이런 형태였는데 그냥 평소처럼 int 형태로 받다가 아예 배열에 값이 저장이 안됐었다. 3. sort 함수를 잘못 사용했다. num의 크기만큼만 정렬시키면 되는데 배열 전체를 오름차순으로 정렬시켰더니 앞에는 0만 들어갈 수 밖에 없었다. 2. return 0;을 빼먹어서 런타임 오류남. 앞으로는 미리 입력하는게 좋을 것 같다. 3. adj 배열의 크기를 너무 작게 잡아서 런타임 오류가 남. 앞으로는 예제만 생각하지 말고 크게크게 잡자! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2.. [백준] 토마토_7576 이 문제를 풀면서 런타임 에러, 컴파일 에러, 메모리 초과, 시간 초과를 모두 볼 수 있었다. 처음에는 한번 모두 토마토들을 옮기고, 하루 동안 옮긴 토마토들을 배열에 저장해서, 다시 그 토마토들을 익은 토마토 배열에 추가하고... 토마토 배열에 변화가 없으면 그만두는 식으로 풀었다. 그 결과 예제들은 맞았지만 메모리 초과 오류가 났다. 동적 할당도 써봤는데도 틀렸다. 결국 다른 블로그를 참고해서 풀었다. 전형적인 BFS 문제였는데, days[1000][1000]이라는 배열을 사용하면 간단하게 풀리는 문제였다. 왜 그렇게 이상하게 풀었을까... 공부가 많이 부족해서 그렇다. 이상하게 풀었던 첫 번째 방법 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22.. 이전 1 다음