백준 1707 - 파이썬
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분 그래프는 인접한 노드끼리 서로 다른 집합에 넣을 수 있다면 이분 그래프이다. 아래의 경우는 서로 다른 집합에 속하므로 이분 그래프가 아니다. 이분 그래프는 처음 접해보는 개념이기도 하고, 풀이 방법도 떠오르는게 없어 구글링을 해봤다. 각 코드의 출처는 제목에 연결해 두겠다. BFS 1 import sys from collections import deque input = sys.stdin.r..
https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 풀이 이번 문제는 어려웠던거 같다. 숨바꼭질1 문제와 다른 점은 최단 경로의 개수도 구해야 한다는 점이다. 풀다가 도저히 모르겠어서 다른 사람의 블로그를 참고했다. 코드 from collections import deque import sys input = sys.stdin.readline n,k = map(int, input().split()) dist..
https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 풀이 처음에 문제를 읽고 이해가 안 되었는데 그림 설명과 함께 보니 금방 이해가 됐다. BFS로 푸는 문제이며 그리디 문제이기에 문제에 나온 조건대로 코딩하면 금방 해결할 수 있다. (코딩하다가 막혀서 다른 사람 풀이 본건 안비밀) 코드 import sys input = sys.stdin.readline from collections import deque graph = [] ..
https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 문제 풀이 이 문제는 문제에서 시키는데로만 하면 풀기 쉬운 문제이다. 구현 순서는 다음과 같다. 1. 양방향으로 각 노드들을 연결한다. 2. 1부터 n까지 완전 탐색하며 리스트의 합이 가장 작은 사람 출력한다(인덱스 출력하면 됨) 3. 합이 작은 사람이 여러명이면 가작 작은 수를 출력 BFS import sys from collections impo..
https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 문제 풀이 이 문제는 삼성 sw 역량 테스트 기출 문제인 연구소3 문제를 풀다가 연구소3은 아직 풀기에 벅찬거 같아서 풀게 된 문제이다. 사실 연구소 2 역시 풀기에 벅찼다. 그래서 다른 사람의 블로그를 참고해 봤다. 문제 풀이의 포인트는 다음과 같다. 1. 그래프를 순회하며 바이러스의 위치를 담는다. 2. 바이러스의 위치를 담은 리스트를 m개의 조합으로 새로운 리스트에 담는다. 3. 조합된 리스트의 위..
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제 풀이 처음에 생각해낸 방법은 예제를 보면 부모노드가 자식노드보다 값이 작게 입력되어 있기에 시작한 값보다 노드가 작을때 부모 노드라 판단하고 조건문을 걸었다. 예제는 모두 맞았지만 오답 처리를 받았다. import sys from collections import deque input = sys.stdin.readline n = int(input()) start, end ..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 문제 풀이 이 문제에서 포인트는 시작 지점이 왼쪽 아래라는 점과 모눈종이에 지정된 범위만큼 색을 칠해주고 탐색을 시작한다는 점이다. import sys from collections import deque input = sys.stdin.readline m,n,k = map(int, input().split()) INF = 1e9 graph = [[INF] *n for _ in..
https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 처음에는 예제 출력을 보고 어떻게 출력한거지 싶어 이해하는데 시간이 좀 걸렸다. 이 문제가 원하는 것은 각 노드의 부모 노드라는 것을 알았고, 입력된 노드들을 양방향으로 연결해 줬다. 그 후 부모 노드를 저장할 리스트와 방문 리스트를 별도로 선언한 후 탐색을 진행하였다. import sys from collections import deque input = sys.stdin.readline n = int(input()) graph = [[] for ..