목록BFS (3)

Written

백준 2206 <벽 부수고 이동하기> C++ 풀이

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한..
알고리즘 문제풀이 2023. 10. 12. 15:47
프로그래머스 / 숫자 변환하기 / C++

처음엔 DFS로 완전탐색 방식으로 구현해봤는데, 테스트케이스 절반에서 시간초과가 나서 BFS로 바꾸었더니 시간초과 없이 전부 맞출 수 있었습니다. 문제를 풀 때, BFS를 사용할 수 있으면 BFS가 높은 점수를 받기에는 더 좋은 것 같습니다. 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 59 #include #include #include #include #include using namespace std; // DFS로 완전탐색때는 시간초과 났었기때문에 B..
알고리즘 문제풀이 2023. 8. 29. 19:25
백준 / 7576 / 토마토 / 알고리즘 문제풀이 / C++

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net BFS를 사용해서 큐에 익힐 수 있는 조건의 토마토의 위치와 익는데까지 걸리는 날짜를 넣고 익힐 수 있는 모든 토마토를 탐색하는 방식으로 풀어보았습니다. 출력을 위해서 zeroCnt라는 변수를 만들어서 0의 개수를 세면서 토마토를 다 익힐수 없는경우와 처음부터 다 익혀져있는 경우에 대해서 정상적으로 출력할 수 있도록 했습니다. 최종적인 날짜 출력은 max라는 변수를 만들어서 큐에있..
알고리즘 문제풀이 2022. 11. 1. 20:17
이전 Prev 1 Next 다음