[Python] 백준 알고리즘 4963번 - 섬의 개수 문제 출처 : https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 접근방식 기존의 DFS / BFS 문제와 유사한 문제이다. 차이점은 이제 대각선의 방향이 추가되어 기존의 4방향 그래프 탐색 문제에서 8방향 탐색 문제로 바뀐 점이다. # 방향 dx = [1, -1, 0, 0, 1, 1, -1, -1] dy = [0, 0, 1, -1, 1, -1, 1, -1] # 탐색 for i in ra..

[Python] 백준 알고리즘 10866번 - 덱 문제 출처 : https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 접근 방식 자료구조를 활용하여 푸는 문제이다. 파이썬에서는 'deque'라는 자료구조를 라이브러리로 지원을 한다. 해당 자료구조에서 지원하는 메서드를 활용해서 문제를 풀면 된다. 문제의 예제를 보면 명령문이 주어져있고, 그러한 명령문 중에 'push'의 계열의 명령문만 뒤에 띄어쓰기 다음에 숫자가 같이 입력이 된다. ..

[Python] 백준 알고리즘 7576번 - 토마토 문제 출처 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 접근 방식 전형적인 그래프 너비 탐색(BFS) 문제이다. 문제에서 요하는 지점, 익은 토마토(1)인 지점에서 각자 0 인 지점을 찾아가며 탐색을 하는 문제이다. 1에서 시작한 탐색은 상하좌우로 탐색을 하며 0인 지점을 찾고 체크하고 넘어간다. 다른 BFS 기본문제와의 차이점은 기본적인 BFS문제는 시작점이 하나였지만..

[Python] 백준 알고리즘 1926번 - 그림 문제 출처 : https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 접근 방식 전형적인 DFS / BFS 방식의 문제이다. 상하좌우 좌표값을 설정하여 하나의 지점마다 조건에 맞는 부분을 찾아가며 풀어가는 구조이다. 문제에서 구하라는 바는 다음과 같다. 1로 이루어진 그림의 개수 -> 0으로 나눠진 부분의 개수를 파악해야 한다 각 그림의 크기를 구하며 그 그림의 크기 중 가장 큰 넓이를 찾아라 다음과 같이 ..

[Python] 백준 알고리즘 11404번 - 플로이드 문제 출처 : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 접근방식 플로이드 와샬 알고리즘을 활용하는 문제이다. 다익스트라 알고리즘이 하나의 노드를 기준으로 각 노드의 최소 가중치를 구하는 알고리즘이라면 플로이드 와샬 알고리즘의 경우에는 전체 노드끼리의 최소 가중치를 구하는 문제이다. 플로이드 와샬의 경우 삼중 반복문을 통해서 다익스트라 알고리즘에 비하면 간단하게 구현이 가능하다. 다만..

[Python] 백준 알고리즘 2407번 - 조합 문제 출처 : https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 접근 방식 파이썬에서 구현이 되어있는 heap 자료구조를 사용하여 문제 코드를 작성하였다. 이번 문제의 경우 구현되어 있는 힙에 숫자를 넣고 빼며 진행이 되는 코드들이다. 0이 들어오면 문제에서 힙에 들어가 있는 가장 작은 수를 출력하면서 빼내는 문제이다. 따라서 0이 들어갔을 때 0만 존재한다면 0이 나오는 경우..