BFS13 [C/C++] 백준 2206: 벽 부수고 이동하기 (BFS,tuple 이용 풀이) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 구현! 사실 원래의 BFS를 이용한 최단거리 알고리즘에서 조금만 추가하면 쉽게 풀 수 있는 문제이다. 여기서 중요한 것은 tuple안의 4개의 원소를 집어넣어 각각 x좌표, y좌표, 벽을 뚫고 지나갔는지에 대한 여부, 현재까지의 거리를 저장해야 하는 것이다. 또한 중요한 것이 visit 배열인데 기존의 2차원으로만 표현하면 안되고 3차원으로 표현하여 벽을 뚫고 지나갔는지에.. 2023. 9. 18. [C/C++] 백준 16236: 아기 상어 (BFS, 반례 및 주의점!) https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 사실 BFS로 돌면서 풀면되는 아주 간단한 문제인줄 알았지만 생각보다 해야할게 많아서 굉장히 고민을 많이 했다. 무려 3시간만에 겨우 풀었다... 문제 해설보다는 내가 실수했던 부분 위주로 한번 써보려고 한다. 주의해야할 점! 1. 지나가는 것과 먹을 수 있는 경우 문제에 그대로 나와있다싶이 자신의 크기보다 큰 물고기가 있는 칸을 제외한 칸은 모두 지나갈 수 있고 자신의 크기보다 작은 물고.. 2023. 9. 17. [C/C++] 13549: 숨바꼭질 3 (BFS,Queue) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 결론부터 말하자면 이 문제는 queue를 이용해 bfs로 풀 수 있는데 이때 2의 배수일 때는 0초만에 도달 가능하다는 것만 유의하면 된다. 구현?? 이를 구현하기 위해서 내가 사용했던 방법은 함수 after_onesec와 after_zero이다. after_onesec는 1초뒤에 갈 수 있는 곳을 queue에 넣는 방식으로 동작되는데 이때 queue.fron.. 2023. 9. 12. [C] 1697: 숨바꼭질 사실 이 문제가 BFS 관련 문제라는 것을 빨리 깨달았다면 구현은 생각보다 쉽게 할 수 있었을 것이다. 그냥 어떻게 풀지 모르겠어서 각 경우의 수를 나누어 구해보고 있었는데 5에서 시작해 17로 가기 위한 경우를 그리던 중 가지가 뻗어지는 tree형태인 것을 확인할 수 있었다. 그리고 몇 초만에 갔는지 확인해야하므로 BFS 관련 문제인 것을 파악했다. 모르겠으면 무식하게 좀 해봐야겠다. 특히 이 문제 같은 경우는 갈 수 있는 방법이 3가지이므로 가지가 3개인 tree인 것을 알 수 있다. 그리고 2차원 배열을 구현할 때 각 index를 써주는 것이 귀찮아서 그냥 처음에 int *ret0=&queue[front][0];로 선언하였더니 코드가 더 깔끔하고 읽기 쉽게 느껴졌다. 또 queue[1000000][.. 2023. 8. 23. 이전 1 2 3 4 다음
