파이썬 백준 16953번 실버2 https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 문제 보기 분류: 그리디 알고리즘, 그래프 탐색, 너비 우선 탐색 문제 풀기 A 에서 B 로 가지 않고 B 에서 A 로 가능한지를 바라보았다. while 을 통해 B 가 짝수일 때는 2 로 나누고, 맨 뒷자리 1 이 있을 때 1 을 제거하여 답을 찾을 때까지 반복한다. 함수 fnConversion() 에 적용된 조건은 다음과 같다. 1. 제일 먼저 B 와 A 가 같은지 비교하여 결과를 내보내고 while 을 멈출 수 있도록 한다. 2. 변환이 불가능한 경우에 대한 조건으로 B 가 A 보다 ..

파이썬 백준 4963번 실버2 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 기존 상하좌우 이웃으로 연결된 문제에서 대각선 네 방향에 대해 추가적 처리를 생각한다. matrix 에서 처음으로 1을 발견하면 fnBFS() 를 실행하여 이웃된 8방향 모두 찾아가 1이 보이면 방문 처리한다. 이렇게 남은 matrix 에 대해 조건을 만족하여 fnBFS() 함수에 들어..

파이썬 백준 7576번 골드5 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색 문제 풀기 BFS 를 사용하여 해결하는 문제이다. 익은 토마토의 위치 좌표를 2차원 deque() 로 먼저 저장을 한다. popleft() 를 통하여 첫 번째 익어있는 토마토의 위치들과 지속적으로 익어가는 토마토의 위치를 순차적으로 꺼내어 모든 매트릭스(그래프)를 탐색할 때까지 반복한다. 이웃하여 다음날..

파이썬 백준 11725번 실버2 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 보기 분류: 그래프 탐색, 트리, 너비 우선 탐색 문제 풀기 루트를 1로 정했기 때문에 1을 부모 노드로 시작하여 그 바로 아래 노드는 1의 자식 노드가 되면서 그 다음 아래 노드의 부모가 된다. 이 규칙을 적용하여 너비 우선 탐색을 이용하여 문제를 해결하였다. 예제 1을 그림으로 나타내면 위와 같다. 위에서 부터 부모 노드 방문을 표시하고 그 아래 자식 노드를 하나씩 deque 에서 꺼내어 부모 노드가 될 수 있는지 (그..