본문 바로가기

BFS13

[C] 7576: 토마토 일단 BFS를 이용하여 초기의 있던 토마토마다 BFS 알고리즘을 이용하여 각 그래프의 점에서 언제가 토마토가 가장 빨리 익는지를 비교하여 배열에 저장하고 마지막에 최댓값을 구하는 방식으로 코드를 짰다. 그렇게 하기 위해 queue_day라는 배열을 생성하여 하루가 지날때마다 하루가 추가되도록 만들었고 새로운 초기 토마토로 BFS를 탐색할 때마다 공통으로 쓰이는 배열들을 초기화해줬다. 또 다 익게 만들 수 없는 경우가 다 익은 경우를 구별해서 구했다. 그래서 그 결과!! 테스트 케이스는 다 맞는데 시간초과가 나오게 됐다.. #include int arr[1001][1001]; int visit[1001][1001]; int queue[1001][2]; int queue_day[1001]; int x_coo.. 2023. 7. 30.
[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.

티스토리툴바