본문 바로가기
728x90

BFS50

[python] 백준 14923 미로 탈출 https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net 문제 해결 전형적인 BFS문제 그러나 편하게 BFS를 돌리면 시간초과가 난다.(벽을 한 번만 깰 수 있다는 것을 활용해야함) 그래서 array를 3차원으로 해서 n*m*2차원을 만든다. (board[i][j][k]: (i,j)에 있고 k개의 magic 사용 가능) 도착점 왔으면 최소이동횟수이므로 cnt출력하면 끝 CODE import sys input = sys.stdin.rea.. 2023. 10. 14.
[python] 백준 3055 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 해결 BFS를 이용하여 푸는 문제라는 것은 쉽게 알 수 있다. 문제는 물과 고슴도치가 동시에 이동한다는 것이다. 그러나 운이 좋게 문제를 잘 보면 물이 올 지역에 고슴도치가 이동할 수 없다고 나오므로 물부터 이동시킨 후 고슴도치를 이동시키면 된다. 고슴도치가 더이상 움직이지 못하면 탈출하지 못하는 것이고 그전에 탈출구를 찾으면 탈출하는데 걸리는 시간을 출력하면 된다. CODE import sys inpu.. 2023. 9. 4.
[C++] 백준 17071 숨바꼭질 5 https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 해결 1초마다 수빈과 동생은 움직인다. 수빈은 1초마다 x-1, x+1 만큼 움직이거나 2*x만큼 순간이동 할 수 있다. 동생은 t초에 t만큼 움직인다. 수빈은 짝수 t초에 있던 지점을 그 이후 짝수 시간 때에 그 지점에 다시 올 수 있다. 홀수 t에 있던 지점은 그 이후 홀수 시간 때에 대사 올 수 있다. 따라서 visited[i][j]에 수빈이 지점 .. 2023. 8. 12.
[python] 백준 23288 주사위 굴리기2 https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 문제 해결 주사위의 움직임을 어떻게 표현할 것인가? 주사위는 입체로 되어있지만 1, 2, 3, 4, 5, 6면이 있다는 것을 알고 있다. 따라서 일차원 배열로 1면 ,2면,3면,4면,5면,6면을 [1,2,3,4,5,6]으로 나타내고 먄약 1면과 3면이 바뀌었으면 dice[0], dice[3] = dice[3],dice[0] 이렇게 바꾸는 것이 편하다. 점수를 계산하는 방법은 같은.. 2023. 7. 16.
728x90