본문 바로가기
728x90

BFS50

[python] 백준 1525 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 해결 표에 숫자를 넣고 빈 곳(0)을 이용해 이동하는 문제 이동 방법은 동서남북이므로 move =[(-1,0), (1,0), (0,-1), (0,1)] 4가지가 있다. 위의 조건과 최소 이동 번수를 구하는 것이므로 아무래도 bfs가 좋다. 그런데 어떻게 풀어야하지?? (ㅜㅜ) 답은 리스트가 아니라 문자열 이용! 1 2 3 4 5 6 7 8 9 위 표는 "123456789" 문자열로 변환 시킬 수 있다! 그리고 n 위치는 (n//3, n%3) 으로 좌표를 만들 수 있다... 2023. 2. 28.
[python] 백준 18352 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 해결 특정 지점까지 가는데 최소 거리가 k인 점을 찾는 문제 (DFS,BFS 다 되지만 거리가 정해져있으므로 BFS로 너비로 찾는 것이 좋다!) 양방향 도로가 아니라는 것에 주의하자! CODE import sys from collections import deque input = sys.stdin.readline n, .. 2023. 2. 26.
[python] 백준 1261 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 문제해결 다익스트라 (bfs를 이용해 꼭지점간의 최소 거리 측정) 벽이 없는 곳은 벽을 깨지 않으므로 비용(cost)가 이전이랑 같다. 따라서 deque()의 왼쪽에 다시 넣는다. 벽을 부시면 비용(cost)를 추가 지불 해야하므로 deque()오른쪽에 넣는다. deque가 없어질 때 까지 반복한 후 m,n 까지 가는데 비용을 출력한다. CODE import sys from .. 2023. 1. 29.
[python] 백준 14226 이모티콘 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제해결 각각의 상황에서 3가지 선택지가 있다. 그렇지만 3가지 선택의 결과가 이전에 나왔던 상황이면(visited 된 상황) 이전의 시간이 더 적게 걸렸으므로 무시할 수 있다. 화면의 길이가 s가 될 때 visited[(now,clip)] 값을 출력하면 된다. CODE import sys input = sys.stdin.readline from collections import deque s = .. 2023. 1. 28.
728x90