넓이우선탐색4 [C] 14940: 쉬운 최단거리 전형적인 BFS 문제로 각 목표지점까지의 거리를 출력하면 된다. 이때 각 거리를 저장하는 배열은 visit를 이용하였고 queue를 이용하여 bfs를 구현하였다. 주의해야할 점은 1.거리를 계산하기 위해 queue[2][] 부분을 거리를 위한 공간으로 할당하였고 queue[2][rear]=queue[2][front]+1; 를 통해 거리를 구할 수 있다. 2. 2가 있던 자리를 visit 배열에서 1로 할당했기 때문에 마지막에 출력하는 부분에서 0이 출력하도록 바꿔야한다. 이건 꼭 좀 잘하자! 맨날 풀었던 문제인데 bfs 구현하는데 이상한 곳에서 시간이 걸렸다. 특히 이번에는 front와 rear을 모두 1로 초기화해놓고 while문 들어가는 조건을 front 반복문 들어가는 조건과 다차원배열 index .. 2023. 8. 21. [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] 10026: 적록색약 그 동안 너무 BFS로만 풀어서 오랜만에 DFS로 풀었다 사실 구역이 몇개인지 알아보는 문제들은 그래프를 다 순회하기만 되기 때문에 BFS를 쓰든 DFS를 쓰든 아무 상관이 없다. 하지만 그래프 내에서 최소로 도달하는 순서나 그래프 순회를 넓이 우선으로 해야하는 경우는 BFS를 써야한다. 사실 아직 많이 풀어보지는 못했지만 DFS로만 풀리는 문제는 보지 못해 헷갈린다면 그냥 BFS를 써야겠다. 그리고 정수를 한꺼번에 배열처럼 받을때 %1d를 사용하면 하나씩 값을 얻을 수 있는데 %1c는 그런게 없다. 항상 배열의 시작이 0인지 1인지 잘생각하면서 풀어야겠다는 생각이 들었다. 또 이 문제와 같이 그래프안의 원소의 값이 달라질때는 아예 clear()함수를 만들어 초기화 시켜주는게 더 깔끔한 것 같다. #in.. 2023. 7. 30. [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. 이전 1 다음