알고리즘/BFS13 [BFS] 백준 14395 : 4연산 - 파이썬 Python https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 생각하기 최소의 변환을 찾으면 되는 문제이기 때문에 BFS로 접근해야겠다고 생각 평소처럼 visited 배열(list)을 통해서 방문 여부를 검사려고하니, 메모리 문제가 발생 -> 각 연산의 특성을 잘 생각해보면 모든 10^9숫자를 다 사용하지는 않음 뺄셈을 만나면 S - S 로 0이 되므로 사실상 끝 나눗셈을 만나면 S / S 로 1이 되므로 사실상 2의 배수가 된다 S^a * 2^b 형.. 2022. 2. 7. 백준 16954번 : 움직이는 미로 탈출 - 파이썬 Python https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 생각하기 시간이 1초씩 지남에 따라서 1. 욱제가 이동하고 2. 벽이 바뀐다 시간이 1초씩 바뀌는 것을 단계별로 나타내기 위해서 bfs를 사용한다 구현하기 큐에다가 row, col 좌표, 흘러간 시간을 묶어서 append 시킨다 큐에서 popleft시키면서 흘러간 시간이 바뀐 경우 체스판의 벽을 한줄씩 내린다 주의할 점 1 체스판의 벽이 한줄씩 내려가다보면 가장 위쪽행은 모두 벽이 없는.. 2022. 1. 1. 백준 14442번 : 벽 부수고 이동하기2 - 파이썬 Python https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 생각하기 bfs 방식을 통해서 가장 먼저 목적지에 도착하면 해당 카운트를 return 하는 방식으로 생각 벽을 부순 횟수 K번에 대한 각각의 visited를 따로 구별해서 표현해야 visited[횟수][row][col] 벽 부순 횟수에 따라 row와 col에 방문한 적이 있는가 체크하여 방문하였으면 중복해서 방문하는 케이스를 줄인다. 구상하기 큐를 사용하여 bf.. 2021. 12. 26. [BFS] 백준 2206번 : 벽 부수고 이동하기 - 파이썬 Python https://www.acmicpc.net/problem/2206 생각하기 미로 찾기와 비슷한 게임이라고 판단하여 BFS를 사용하여 마지막 정점까지 가는 최소를 구하기로 생각했다 미로 찾기 문제와 달리 까다로운 해결해야할 조건 하나는 "벽을 한개 깰 수 있다는 점" 각 정점에서 다른 정점으로 이동하는 경우는 다음과 같다 빈칸 -> 빈칸 : 벽 깨기 유무와 상관 없이 모두 이동 가능 빈칸 -> 벽 : 벽 깨지 않은 경우 만 이동 가능 / 벽을 깬 경우 이동 불가 벽 -> 벽 : 이동 불가 벽 -> 빈칸 : 벽 깨기 유무와 상관 없이 모두 이동 가능 백준 강의에서 정점이란 정점은 앞에 어떤 상황이건 간선에 대하여 항상 같은 일을 해야 함 이 정의가 지켜져야 정점이라는 것이 성립한다 따라서 큐에 넣어주는 정점.. 2021. 11. 21. 이전 1 2 3 4 다음
