반응형

BFS 2

[백준 12851번][Python] - 숨바꼭질 2

https://www.acmicpc.net/problem/12851 # 풀이과정 (BFS 이용)수빈이가 이동하는 방법은 앞으로 한칸, 뒤로 한칸, 현재 칸의 두배 위치로 점프, 이렇게 3가지이다.각 위치에 도달하기 위한 최소 시간을 나타내는 리스트를 하나 설정최단 시간을 구해야 하기에, 현재까지의 최소시간을 의미하는 전역변수 maxCnt를 설정함최단 기록의 경우의 수를 나타내는 변수 num을 설정함BFS를 이용하여 큐에 수빈이가 동생을 잡기위해서 현재까지 소요된 시간 및 현재위치를 넣음이것을 반복하여 동생의 위치에 도달하게 되면, 그때를 기준으로 소요된 시간이 총 걸린 시간임maxCnt보다 현재 소요된 시간이 크다면, 해당 경우의수는 더이상 계산하지 않음각 위치별로 도달에 필요한 최소 시간을 나타내는 리..

백준 2024.11.03

[백준 17070번] - 파이프 옮기기 1 (Python)

https://www.acmicpc.net/problem/17070         # BFS풀이과정1. 제한시간은 1초, bfs를 이용하여도 N의 크기가 그렇게 크지 않기에 BFS를 이용2-1. 파이프는 가로상태에서 가로, 대각선방향으로 밀 수 있음2-2. 세로상태에서는 세로, 대각선으로 밀 수 있음2-3. 대각선 상태에서는 모든 방향으로 밀 수 있음3. 각각의 방식대로 밀고 나서의 파이프의 상태, 행, 열을 튜플로 묶어서 큐에 저장4. 만약 행,열이 모두 N이 된다면 카운트를 1증가시킴5. 최종 카운트를 출력 ***주의점***대각선으로 밀 때는 오른쪽, 대각선아래, 아래, 총 3개의 칸에 전부 벽이 없어야함  위와 같은 생각으로 BFS를 이용하여 코드를 짰다.  [BFS를 이용한 코드 - 시간초과]# ..

백준 2024.09.09
반응형