전체 글
-
1679 숨바꼭질알고리즘/백준 문제 2020. 5. 16. 13:43
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 이 문제 역시 최소시간(최단거리)를 구하는 문제이기 때문에 BFS를 이용해서 풀었다. 큐에 들어갈 다음 경로는 문제에 나와 있듯이 3가지가 있다. x+1 x-1 x*2 이전 BFS문제들과 같은 방식인데, 다른 문제에서 동서남북으로 움직이던 것을 이 문제에서는 위의 3 가지 경우로 움직이면 되고 일직선 상의 경로니까 1차원 배열을 사용했다. 때문에 오히려 쉬웠다. 아! 그..
-
7576 토마토알고리즘/백준 문제 2020. 5. 16. 00:16
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 기본 BFS 문제와 달라진 점은 출발점이 0,0이 아니면서 동시에 탐색을 해야하는 점 이전에는 출발점을 이중 for문으로 찾아서 한번 실행시켜주면 되었다. 이번에는 출발점이 여러개 일 수 있기 때문에 이중 for문으로 찾은 출발점들을 바로 넘겨주지 않고, 큐에 저장했다. 그 뒤로는 똑같음 딱히 어려운 점은 없었다.
-
2667 단지번호붙이기알고리즘/백준 문제 2020. 5. 15. 03:14
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 이전에 풀었던 BFS 문제들과 비슷한데, 다른점은 출발점이 정해져 있지 않다. 그렇기 때문에 이중 for문을 만들어서 모든 지점을 출발점으로 하여 BFS를 실행한다. BFS 함수 내부에서는 초반에 방문한 좌표가 들어오면 종료시켜준다. 종료되지 않았다면 단지가 형성되어 있다는 의미이므로, while문 안에 for문을 돌때마다 단지의 아파트수 (cnt)를 증가 함수를 종료하기 전에 List에 cnt값..