본문 바로가기

graph5

[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.
[C] 1012: 유기농 배추 이 문제도 결국 앞서 풀었던 2667 단지번호붙이기 문제와 매우 유사하다. 단지의 수를 구한 것과 마찬가지로 이 문제도 배추의 집단의 수를 구하면 됐던 것이고 이를 위해서 BFS 알고리즘을 활용하여 풀었다. 다만 여기서 주의해야 했던 점은 배추의 배치가 고정되어 있지 않고 테스트케이스마다 달라지기 때문에 그때마다 다시 arr과 visit 배열을 초기화 해줘야 했던 것이다. #include int visit[51][51]; // 지나갔는지 확인 int arr[51][51]; //그래프를 저장 int queue[2800][2]; int x_jump[4]={1,0,-1,0}; //오른쪽, 아래로, 왼쪽, 위로 int y_jump[4]={0,1,0,-1}; int bfs(int max_y,int max_x,in.. 2023. 7. 30.
[C] 2667: 단지번호붙이기 이 문제는 앞서 풀었던 미로 탐색 문제와 매우매우매우 흡사하다 공통점으로는 일단 그래프 끝까지 모두 탐색을 해야하고 이걸 저정해야하며 BFS 알고리즘을 사용해서 풀어야했던 것인데 사실 DFS 알고리즘을 써도 풀렸을 것이다. 그래도 미로탐색 문제가 생각이 나서 BFS로 풀게 돠었다 BFS 알고리즘을 사용할 떄 전역 변수를 잘 사용해야하고 nx,ny를 잘 사용하여 범위를 정해 최대한 간결하면서도 이해하기 쉽게 코드를 정리하는게 중요한 것 같다. 또한 queue 배열을 사용해야하는데 아직 이에 익숙치 않아 더 공부해야겠다. 차이점으로 미로탐색 문제는 맨 마지막 좌표까지 도달하는 최단 경로를 찾는 문제였고 이번 문제는 단지를 찾아서 단지 안에 있는 아파트를 찾는 것이다. 또 다른 차이점은 여러가지 그래프가 생성.. 2023. 7. 29.
[C] 2606: 바이러스 앞서 DFS와 BFS 관련 문제를 풀어서 그런지 구현하는데 크게 어려움을 받지는 않았다. 사실상 앞선 문제와 똑같이 구현 했다고 봐도 무방하다. 주의해서 할 점은 어떤 것을 전역변수로 사용할지와 포인터를 함수의 매개변수로 넣을때 어떻게 할지 좀 더 노력해야 한다는 점이다. BFS나 DFS 둘 중 아무거나로 구현해도 상관없는데 이번에는 그냥 좀 더 쉬운 DFS를 이용해서 풀었다. #include int visit[101]; int arr[101][101]; void dfs(int arr[][101],int* cnt, int n, int V) { int result; for(int i=1;i 2023. 7. 29.

티스토리툴바