https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 아파트 층을 한 방향으로 연결된 그래프(리스트) 라고 생각을 하고 BFS로 풀면 간단히 풀 수 있는 문제이다. graph 배열을 만들어서 INF로 채워넣고, 처음 방문하게 되면 이전 위치의 값에서 1을 더한 값을 저장했다. import sys from collections import deque input = sys.stdin.readline F, S, G, U, D = map(int, input().spli..
알고리즘💻/그래프(DFS&BFS)
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 신장트리를 구하는 기본적인 문제이고, 나는 크루스칼 알고리즘을 이용하여 풀었다. 가중치 값을 기준으로 오름차순으로 정렬한 후 간선의 두 정점이 서로 다른 그래프인 경우 해당 간선을 선택해나가는 알고리즘이다. 두 정점이 서로 연결되어있는지 여부를 확인하는 check 함수를 만들어서 사용했고 DFS를 이용하였다. python으로는 시간초과가 났고, pypy3로 통과했는데 아무래도 check를 DFS말고 다르게 탐색하면 시간을 더 줄일 수 있을 것 같다. import sys input ..
https://www.acmicpc.net/problem/22352 22352번: 항체 인식 첫 번째 줄에는 SP 촬영 결과의 크기를 의미하는 두 정수 $N$과 $M$이 주어진다. ($1 \le N, M \le 30$) 이는 촬영 결과가 세로로 $N$칸, 가로로 $M$칸 크기의 격자라는 것을 의미한다. 다음 $N$개의 줄에는 www.acmicpc.net 백신을 맞기 전(before)과 맞은 후(after)의 배열의 원소를 비교하다가 다른 원소가 나오는 경우에 해당 원소에 백신을 맞은 것으로 가정하고 백신을 맞아서 변화된 데이터는 after의 원소값이라 생각하고 dfs를 통해 해당 원소부터 상하좌우로 갈 수 있는 모든 before의 원소의 값을 바꾼다. dfs를 실행한 후 다시 before와 after의 ..
https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net DFS를 기둥의 길이를 찾는 데 한번, 그리고 가지 길이의 최댓값을 찾는 데 또 한번 총 두 번을 써서 해결할 수 있는 문제였다. 인접리스트를 이용하여 데이터를 받았고, 스택(q)에 탐색노드와 해당 노드까지의 거리를 추가하는 방식으로 풀었다. 처음에 런타임에러(TypeError)가 나..
https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net n*m의 배열의 각각의 지점에서 목표지점까지의 최단거리를 출력하는 문제이다. 거꾸로 생각하면 목표지점에서 각각의 지점까지의 최단거리를 출력하는 문제가 되기 때문에, 목표지점을 시작 인덱스로 놓고 BFS탐색을 이용하여 풀 수 있다. queue를 이용한 반복문 반식으로 BFS를 구현하였고, 처음에는 도달하지 못하는 곳은 모두 -1로 출력을 하도록 만들어서 ..
https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net DFS와 브루트포스를 이용하여 풀 수 있는 문제였다. 주어진 숫자판의 모든 원소를 시작점으로 하여 해당 시작점의 인덱스를 DFS 함수의 변수로 주었다. DFS 함수 안에서는 가능한 방향으로 움직여 다시 DFS 를 재귀 호출하였고, 움직인 횟수가 5가되면 만들어진 문자열을 ans 배열에 추가한 후 리턴하였다. 이때 인덱스 오류가 나지 않도록 체크해주어야 한..
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 비행기의 종류가 최소가 되어야 한다고 해서 순간 헷갈렸는데, 그냥 dfs로 그래프를 탐색하면서 모든 나라를 방문할때까지 이동하는 횟수를 카운트하면 되는 간단한 문제였다. import sys input = sys.stdin.readline T = int(input()) def dfs(v): global cnt, ans visit[v] = True cnt += 1..
https://www.acmicpc.net/problem/21316 21316번: 스피카 위 그림은 처녀자리 중 12개의 별을 12개의 선분으로 이어 만든 그림이다. 시은이는 임의로 각 별에 1부터 12까지의 서로 다른 정수 번호를 부여하고, 12개의 정수 쌍으로 각 선분이 어떤 두 별을 www.acmicpc.net 알고리즘 분류에는 그래프이론, 애드 혹(ad-hoc) 이라고 써있는데, 애드 혹이 뭔가 해서 검색해보니 정형화된 방법론이 아니라, 그 문제를 풀기 위한 창의적인 아이디어를 떠올려야 하는 경우에 애드혹 문제 라고 한다고 한다. 해당 문제도 풀 수 있는 방법이 여러 개 있을 것 같은데, 나는 인접리스트 방식으로 그래프를 받은 후에 1~12까지 탐색하면서 연결된 원소가 3개인 경우에 그 각각의 원..
https://www.acmicpc.net/problem/14496 14496번: 그대, 그머가 되어 첫째 줄에 머호가 바꾸려 하는 문자 a와 b가 주어진다. 둘째 줄에 전체 문자의 수 N과 치환 가능한 문자쌍의 수 M이 주어진다. (1
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 풀이: BFS를 사용해서 그래프를 탐색하면서 최단 거리를 dist[] 배열에 저장하였고, 탐색이 끝난 후에 dist 배열을 돌면서 값이 K인 경우를 출력하였다. K인 경우가 없을 때는 -1을 출력하였다. import sys from collections import deque N, M, K, X = map(int, sy..
