자바 백준 2644번실버 2https://www.acmicpc.net/problem/2644     문제 보기분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색     코드 풀이import java.util.Scanner;import java.util.ArrayList;public class Main { // 그래프를 표현하는 인접 리스트 static ArrayList[] graph; // 방문 여부를 저장하는 배열 static boolean[] visited; // 촌수를 저장하는 변수, 초기값은 -1 static int result = -1; public static void main(String[] args) { Scanne..

파이썬 백준 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 에서 꺼내어 부모 노드가 될 수 있는지 (그..

파이썬 백준 13023번 골드5 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 문제 보기 분류: 그래프 탐색, 깊이 우선 탐색 문제 풀기 사람 다섯명이 연속적으로 주루룩 4번 이상의 연결이 형성되면 문제에서 제시한 관계가 만족한다. 맞으면 1, 아니면 0. 주어진 입력을 graph (relationships) 로 저장하여 모든 사람에 대해 연속 4번의 관계가 만족하는지 모두 탐색해 본다. 이때, DFS 가 재귀함수로 4번이 실행되면 fnDFS 를 result == True 로 나와 관계를 만족하여 1 을 출력하고, 그렇지 않고 4번의 재귀가 일어나..

파이썬 백준 10026번 골드5 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 2667번 단지번호붙이기 문제와 비슷하다. 지난번엔 집이 있는 위치를 표시한 숫자 1에 대해 DFS 를 실행하였다면, 이번 문제 적록색약에서는 방문여부에 대해서 그리고 다른 문자 즉 다른 색이 나오는지 까지 확인하여 DFS 를 돌린다. 색약이 아닌 경우와 색약인 경우를 분리해서 다뤄..

파이썬 백준 11724번 실버2 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 문제 보기 분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 "연결 요소의 개수" 라 하면 아무리 생각해도 간선의 개수밖에 떠오르지 않는다. 요소라 한다면 그 느낌은 더욱 작아지는 방향으로 나아가는 단위 물체 아닌가.. 문제 이해 부족으로 인해 검색을 해보고 서로 관련 없이 완전 분리된 ..

파이썬 백준 2667번 실버1 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 보기 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 그래프 탐색을 하는 문제이다. 연습을 위해 DFS 방법으로 접근을 하였다. 주어진 예제 입력에 따라 2차원 리스트로 집의 위치를 모두 town_map_input 에 입력받는다. town_map_input = [list(map(str, inputdata().split())) for..

파이썬 백준 1012번 실버2 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 보기 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 풀기 이 문제를 DFS 로 풀기 위해서 sys.setrecursionlimit(10000) 모듈을 추가해야 한다. 파이썬 기본 재귀 한도는 1000 이기에 재귀 깊이가 1000을 넘어가게 되는 경우 런타임 오류가 발생한다. 주어진 배추의 위치를 matrix 2차원 리스트에 저장한다. 이때 문제에..