자바 백준 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..

파이썬 백준 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차원 리스트에 저장한다. 이때 문제에..

파이썬 백준 2606번 실버3 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 보기 분류: 그래프 이론, DFS 문제 풀기 작동방식은 이해를 하였으나 아직 코드 형태가 친근하지 않은 DFS 로 접근해보는 문제이다. 컴퓨터의 개수와 연결된 개수를 입력 받고 연결된 두 노드간의 정보를 저장하기 위한 2차원 매트릭스를 작성한다. 그리고 컴퓨터의 개수보다 1개 더 많게 0으로 채워진 visited_dfs 를 만든다. (index 번호와 컴퓨터의 번호를..