본문 바로가기
728x90

BFS50

[python] 백준 16953 A->B https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 해결 전형적인 가장 쉬운 완전탐색 문제라 생각했다. bfs가 dfs보다 편할 것이라 생각했다. heapq, deque 어떤 것을 써도 상관 없다.(근데 deque가 속도가 더 빨랐다.) CODE from collections import deque import sys INF = sys.maxsize a, b = map(int, input().split()) ans = INF def bfs(): global ans que = deque() que.append((a,0)) while que: x, cnt = que.po.. 2023. 3. 11.
[python] 백준 14503 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제 해결 한칸씩 정해진 규칙대로 움직이면서 청소 안된 곳 청소하는 것으로 구현하는 문제 사실 어렵진 않지만 처음 원본 그대로 deepcopy를 해야한다. 그 이유는 처음 0, 1은 단순히 청소 안된 곳, 청소 된 곳을 의미하는 것이 아니라 이동할 수 있는 곳, 이동 할 수 없는 곳(벽)을 의미하는 것이기도 하기 때문이다. 따라서 아래 코드는 vi.. 2023. 3. 7.
[python] 백준 14502 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 벽을 어떻게 세워야하는가? → 상황에 따라 다르다. So 모든 경우 다 해봐야 한다. 재귀 사용! 최대 영역을 어떻게 구하는가? 전염 되는 지역을 계속 이동 시킨 후 더이상 전염이 안될 때 전염이 안된 일반 지역의 구역 개수를 구하면 된다. 전염지역 구하기 위해 bfs() 할 때 계속 graph 값이 바뀌므로 copy.deepcopy를 이용해 복사본으로 돌리는 것이 좋다! copy 라이브러리 알아두.. 2023. 3. 6.
[python] 백준 2251 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 해결 하노이탑 같은 문제 느낌이 들었다. x+y+z = c (c는 상수)이므로 x,y를 변수로 두면 z는 알아서 구해진다. bfs문제로 푸는 것이 좋을 듯 싶다. CODE from collections import deque sender = [0, 0, 1, 1, 2, 2] receiver = [1, 2, 0, 2, 0, 1] limit = list(map(int, inp.. 2023. 2. 28.
728x90