파이썬15 [백준]BOJ 4179: 불! - Python/BFS https://www.acmicpc.net/problem/4179 문제풀이지훈이가 움직이고, 불을 퍼뜨리면 된다. 순서대로 진행하면 되는데 주의해야 할 점이 두 가지 있다.1. 1분마다 기준으로 번갈아서 움직여야 한다.2. 지훈이가 움직이기 전에 불에 타면 안된다.코드from collections import dequedef bfs(jihun, fires): is_jihun_Visited = [[-1] * c for _ in range(r)] fire_queue = deque() jihun_queue = deque() fire_queue.append(fires) jihun_queue.append([jihun]) is_jihun_Visited[jihun[0]][jih.. 2024. 6. 10. [백준]BOJ 14891: 톱니바퀴 - Python 14891번: 톱니바퀴 (acmicpc.net) 14891번: 톱니바퀴첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터www.acmicpc.net문제위 링크 참조풀이설명이 불친절하고 매우 비직관적이므로 문제를 잘 읽어야 한다. 딱히 필요로 하는 알고리즘은 없고, 구현 능력 자체도 크게 요구하지 않는다. 그냥 문제를 이해하는것 자체가 이 문제의 가장 큰 난관이지만, 그렇다고 국어문제도 아닌게 애초에 문제가 말이 안된다. 이 문제에서 톱니바퀴는 절대로 현실의 톱니바퀴처럼 움직이지 않는다. 이전 톱니바퀴가 회전하면 다음 톱니바퀴도 회전해야할지 말아야 할지를 이미 .. 2024. 4. 19. [백준]BOJ 14890: 경사로 - Python/구현 14890번: 경사로 (acmicpc.net) 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 길어서 생략, 위 링크 참조 풀이 경사로의 방향을 생각해보면 왼쪽에서 오른쪽으로 올라가는 방향이 있을 것이고, 그 반대인 오른쪽에서 왼쪽으로 올라가는 방향도 있을 것이다. 이러한 경우에는 한 번에 해결하기 보다는 배열을 정방향, 역방향으로 각각 순회하여 경사로를 만들어주는 것이 좋다. 따라서 알고리즘은 다음과 같다. 1. 주어진 2차원 배열을 Transpose한 배열을 하나 더 만든다. 세로 모양의 길을 찾기 위해서이다. 2. 정방향으.. 2024. 4. 19. [백준]BOJ 14499: 주사위 굴리기 - Python 14499번: 주사위 굴리기 (acmicpc.net) 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 풀이 특별한 알고리즘이나 문제 해결 기법을 사용할 필요 없이, 순수하게 딕셔너리 자료구조만을 사용해서 풀 수 있는 문제이다. 주어진 주사위의 전개도를 이용하여 각 면에 숫자를 붙이고(면에 써져있는 숫자가 아닌 각 면을 인식하게 해주는 숫자, 이하 ID숫자라고 하겠다.) 이를 방향: ID 숫자의 꼴로 딕셔너리를 생성한다. 또 ID숫자: 면에 .. 2024. 4. 15. [백준]BOJ 5558: チーズ (Cheese) - Python/BFS 5558번: チーズ (Cheese) (acmicpc.net) 5558번: チーズ (Cheese) 入力は H+1 行ある．1 行目には 3 つの整数 H，W，N (1 ≦ H ≦ 1000，1 ≦ W ≦ 1000，1 ≦ N ≦ 9) がこの順に空白で区切られて書かれている．2 行目から H+1 行目までの各行には，'S'，'1', '2', ..., '9'， www.acmicpc.net 문제 + 파파고 번역 풀이 처음에 문제를 읽었을 땐, 치즈를 먹는 순서를 어떻게 정해야 하나 싶었지만, 시작 할 때 쥐의 체력이 1 고정이므로 고민할 필요 없이 1, 2, 3, ..., N 순서대로 먹으면 된다. BFS를 이용하여 시작 지점에서 시작해서 각 치즈간의 거리를 순서대로 더하면 된다. 코드 from collections import .. 2024. 4. 12. [백준]BOJ 15591: MooTube(Sliver) - Python/BFS 15591번: MooTube (Silver) (acmicpc.net) 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제 풀이 문제가 쓸데없이 복잡하게 설명되어 있다. 중요한 것은 모든 노드가 연결되어 있고 웨이트를 가진 엣지가 존재하지만, 두 노드간의 거리는 경로상의 가장 작은 웨이트를 가진 엣지가 된다. 따라서 웨이트가 있다 해서 다익스트라를 쓸 필요가 없다. 들어오는 쿼리마다 BFS를 이용하여 그래프를 탐색하고 두 노드간의 거리는 실시간으로 업데이트 해.. 2024. 4. 12. [백준]BOJ 10021: Watering the Fields - Python/Kruskal 10021번: Watering the Fields (acmicpc.net) 10021번: Watering the Fields Input Details There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor will only install pipes of cost at least 11. Output Details FJ cannot build a pipe between the fields at (4,3) and (5,0), since its cost would be only 10. He therefore b www.acmicpc.net 문제 + 파파고 번역 풀이 "모든 필드를 파이프 네트워크로 연결하는 데 필요한 최소 금액"에서 MS.. 2024. 4. 12. [백준]BOJ 1726 - 로봇 - Python/BFS https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 로봇이 바라보는 방향에 따라서 갈 수 있는 노드가 달라진다 -> 3차원 그래프다 (세로 m, 가로 n, 높이가 4인) 이 발상만 빠르게 해낸다면 평범한 BFS 문제가 된다. 하나의 노드에서 최대 5개의 노드와 연결이 가능하다(회전 2방향, 전진 3방향) 하지만 2칸 이상 전진했을때, 앞선 칸이 1이면 넘어가지 못한다. (점프를 할 수 없다) 이것만 주의하고 BFS 탐색을 하면 쉽게 결과를 낼 수 있다. # .. 2022. 11. 18. [백준]BOJ 3055 - 탈출 - Python/BFS https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 입력으로 그래프가 주어지고, 어느 칸에서 BFS를 시작해야하는지 알려준다. 문제를 읽어보면 고슴도치와 물 둘 다 BFS 탐색을 해야 하는 것을 알 수 있다. 주의할 점은 예제에는 초기에 물인 칸이 1개밖에 없지만 문제를 읽어보면 1칸이라는 제약조건이 없다. 따라서 물이 여러칸일 때도 생각하고 프로그래밍을 해야 한다. 처음에 두가지 생각을 했다. A. BFS탐색을 각각 따로 하는 방법 1. 고슴도치를 먼저 BF.. 2022. 11. 17. 이전 1 2 다음
