코드19 [C] N과 M 백트래킹(Backtracking): 해를 찾는 도중에 지금의 경로가 해가 되지 않을 경우 그 경로를 더이상 가지 않고 되돌아오는 것! -> 모든 가능한 경우의 수 중 특정 조건을 만족시키는지 확인 -> 특정 조건 만족안하면 탐색 X -> DFS등에서 모든 경우의 수를 탐색하는 과정에서 같이 사용하여 더 이상 아니면 그 이전으로 돌아가서 다시 탐색 -> 조합과 관련된 문제는 백트레킹! -> 자기 자신을 호출하는 재귀함수를 주로 이용, 탈출 조건 잘 써야함! 15650 N과 M(2) -> 중복 안됨 -> 오름차순 #include int arr[11]; void ascend(int front,int n, int m, int cnt) { for(int i=front;i 2023. 8. 5. [C] 7569: 토마토 7576 토마토 문제와 거의 유사하지만 전에 문제는 2차원 배열, 이번 문제는 3차원 배열로 풀어야한다는 점에서 다르다. 전에 코드에 비해 나아진 점을 찾아보자면! 1. graph 값을 저장하면서 동시에 익은 토마토가 있는 경우에 바로 queue에 저장해뒀고 2. 몇번째 날에 익었는지를 새로운 배열로 선언하지 않고 queue 배열을 [][4]로 지정하여 0에는 z, 1에서 y, 2에는 x, 3에는 익은 날짜를 저장함으로써 가독성을 높였다. 3. 익은 토마토 개수와 토마토가 없는 자리의 개수를 따로 구함으로써 예외인 경우를 처리해줬다. 주의해야할 점을 찾아보자면! 3차원 문제이기때문에 Z,Y,X 순서를 헷갈리지 않아야하고 맨 마지막에 bfs()함수에서 return 할때 queue[rear][3]에는 아무런.. 2023. 8. 4. [C] 1389: 케빈 베이컨의 6단계 법칙 일단 인접행렬로 그래프를 저장한다음에 for문을 이용하여 언제가 베이컨 수가 가장 작은지를 확인해봤다. 나아진 점1: 처음에 bfs를 돌릴때 queue에다가 먼저 놓고 bfs함수를 호출함으로써 dfs와 bfs를 섞어쓰던 실수를 없앴다! 나아진 점2: bfs함수에서 beacon_number을 구할때 따로 배열을 만들어 몇번째에 beacon_number에 넣었는지 저장해두었는데 이번에는 beacon_number[i]=beacon_number[tmp]+1; 를 사용하여 배열 2개로 저장하던걸 1개로 저장하여 효율성을 높였다. 나아진점 3: bfs 만드는 속도가 빨라졌고 continue의 사용을 적절히 했다! 그리고 그래프에서의 최단거리를 구할 때는 항상 BFS를 쓴다는 것을 잊어버리면 안된다!! #includ.. 2023. 8. 3. 이전 1 2 3 4 5 다음