본문 바로가기

백준28

백준 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] 백준 12886번 : 돌 그룹 - 파이썬 Python (보충예정) 생각하기 돌 그룹이 모두 같은 개수가 있는지를 찾는 문제이기 때문에 DFS 와 BFS 중 고민했다. 최소를 구하는 문제는 아니지만 그룹의 개수가 같아지면 바로 프로그램을 종료하면 된다고 생각했다 만약 DFS를 사용한다면 그게 그룹의 개수가 절대 같아지지 않는 경로를 탄다면 굉장히 오버헤드가 커질 것이라 생각했다 BFS로 A, B, C 조합의 주변부터 검사를 했을 때, 그룹의 개수가 같아지는 상황이 걸리면 바로 종료하기로 했다 구현하기 큐를 만들어서 해당 조합이 같지 않고 개수가 달라서 로직이 실행되고 검사시, 문제가 없다면 큐에 넣어주어서 BFS를 구현한다 visited 배열 만약 조합이 이전에 했던 조합이 또 나오면 결국 그 안에서 반복되어 무한루프가 생기기 때문에 visited 여부를 체크해가며 BF.. 2021. 11. 18.
[BFS] 백준 14502번 : 연구소 - 파이썬 Python 생각하기 처음에는 어떻게 벽 3개를 놓으면 하면 바이러스의(2번의) 확산을 적게할 수 있을까에 대해서 생각했다 하지만 고려해야할 변수가 너무 많았다. 벽이 놓였을 때, 어떤 기준으로 해당 자리에 있을 때, 확산이 최소가 되는지 벽이 한개도 아니다 세개인데 한개가 맞으면 다른 두개는 어떻게 판단할건지 코드가 복잡해지면 다시 생각하자.. 다시 생각하는게 좋았다 만약 벽 3개를 N x M 개의 좌표의 각 칸을 대상으로 3개를 뽑는 조합을 구성한다면 M이 최대가 8이므로 64 x 63 x 62가 되겠다 해당 조합을 기준으로 각각의 바이러스들을 BFS로 하여서 모든 조합 벽배치 조합을 검사하는 방식으로 진행을 하여도 64 x 63 x 62 x 64 < 1억 이므로 충분히 시간안에 해결이 가능하다 구현하기 iter.. 2021. 11. 17.

티스토리툴바