문제 링크 https://www.acmicpc.net/problem/13424 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 풀이 다익스트라 알고리즘을 활용해 풀었습니다. (line 6~17) 인접 행렬 adj 에 양방향 간선을 표시해줍니다. (line 26~27) 반복문을 돌려 1부터 n 번 방까지 다익스트라를 구합니다. (line 30~32) [해당 방(i) -> 각 친구들의 방 위치] 까지 이동할때의 최단 거리 합을 구합니다. (line 32) ans[i]에는 i까지 친구들의 이동거리의 총합이 저장되어 ..
Koala - 5기/코딩테스트 준비 스터디
문제링크 문제 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 출력 첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다. 예제 입력 1 4 6 1 2 3 2 3 3 3 4 1 1 3 5 2 4 5 1 4 4 2 3 예제 출력 1 > 7 Solution 도착지점을 가는데 ..
* 개인 블로그에 작성한 내용을 복사해왔습니다. [Algorithm] BOJ 23354 BOJ 23354번 물통다익스트라를 사용하여 풀이하면 되는 문제입니다. 처음에는 순열을 사용하여 각 순서대로 다익스트라를 돌려 풀이하였는데, 당연히 시간 초과가 떴습니다.그래서 탈영병 인원만 velog.io BOJ 23354번 군탈체포조 23354번: 군탈체포조 군탈 체포조(Deserter Pursuit)란 탈영병을 추적/체포하는 군인들을 말하며, 줄여서 DP 라고도 한다. 어느 날 군탈 체포조인 호열이에게 활동비와 지도를 주고 탈영병들을 모두 잡아 부대에 복귀하라 www.acmicpc.net Intro 다익스트라를 사용하여 풀이하면 되는 문제입니다. 처음에는 순열을 사용하여 각 순서대로 다익스트라를 돌려 풀이하였는데..
https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 풀이 처음에는 맥도날드와 스타벅스가 없는 정점들을 순차적으로 출발점으로 두고 반복문을 사용하여 맥도날드와 스타벅스의 최단거리의 합을 각각 구했다. 하지만 이 풀이는 시간 초과라는 결과를 가져와 다른 방식으로 접근해야겠다고 생각했다. 먼저 맥도날드에 대해 모든 맥도날드 위치를 출발점으로 두고 최소힙을 사용하여 각 정점들에 대해 거리를 구했다..
문제 https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 풀이 구현 + 브루트포스 알고리즘 문제이다. 문제 조건을 꼼꼼히 읽지 않아서 많이 틀렸는데 오답률이 낮은 이유가 있다.. 북동, 동, 남동, 남 방향으로 확인하면 되는데 범위를 넘어가는 경우나 6개이상 놓여 있으면 안되는 조건을 꼭 숙지해야한다 코드 #include using namespace std; int board[20][20]; // 범위 안에 있는지 확인하는 함수 bool insid..
문제 풀이 주어지는 노선이 양방향이므로 다익스트라 알고리즘을 3번 이용하여 풀었습니다. 입력받는 위치는 총 4가지 입니다. 1과 N, 필수로 들러야 하는 start와 end. 다익스트라 알고리즘을 1, N, start 에서 이용하여 각 경로로 가는 최단거리를 구합니다. 여기서 1 -> start + N -> end 와 1 -> end + N ->start 를 비교하여 더 작은 값을 얻습니다. (start -> end는 동일, 양방향) 이 값에 start -> end 의 최단거리를 더하여 답을 얻습니다. 예외 처리) start가 1과 같은 경우, end와 N이 같은 경우엔 해당 연산을 삭제합니다. 코드 import java.io.*; import java.util.*; class Main { static ..
문제 링크 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 파이썬의 deque 모듈을 이용해 BFS를 구현하였다. BFS를 하기 전 memo 변수에 W팀의 탐색을 진행하는지, B팀의 탐색을 진행하는지 기록하였다. (line 16) 탐색 조건으로 memo 변수에 저장된 팀에 속한 병사인지 체크한다. (line 24) num 변수는 모여있는 병사들의 수를 센다. (line 15) 탐색 조건을 만족하면 num 수를 1씩..
문제링크 예제 입력 1 5 RRRBB GGBBB BBBRR BBRRR RRRRR 예제 출력 1 4 3 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다. 적록색약 : G,R을 구별 못 함 Solution Base: 깊이 우선 탐색을 사용하여 R,G,B 일 때를 모두 탐색 def bfs(x,y,color): global isvisited isvisited[x][y] = True dx = [0,1,0,-1] #위 아래 왼쪽 오른쪽 방향 설정 dy = [1,0,-1,0] for i in range(4): mx = dx[i] + x my = dy[i] + y if 0
문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 dfs와 bfs에 대한 기초를 점검하는 문제이다. 그래프를 인접행렬과 인접리스트로 나타낼수 있는데, 인접행렬보다 인접리스트가 메모리 측면에서 더 좋기때문에 벡터를 이용하여 구현하였다. 입력받을때 양방향 그래프이므로 양쪽모두에 간선을 넣어주고, 각 노드 벡터마다 정렬을 해준뒤 구현하면 된다. 코드 #include #include #include #in..
https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net [풀이] 나이트가 이동하는 방향만 잘 고려한다면 결국 최단 거리를 찾는 문제와 동일하기 때문에 전형적인 BFS 문제입니다. 다른 기본적인 BFS 최단거리 문제에서 사용하는 상하좌우로 이동 대신 나이트가 이동 가능한 8방향으로 이동하며 탐색합니다. 목적지까지의 Depth를 찾으면 되는 간단한 문제였습니다. 더보기 #include #include #include using namespace std; i..
문제 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 풀이 가장 처음에 생각난 풀이는 n^3 * logn의 풀이인데 (임의의 세수 합을 구해서 이분탐색으로 찾기) n 이 최대 1000이기 때문에 시간초과가 난다. 정답을 구하기 위해서는 n^2 또는 n^2logn의 풀이를 생각해야 했고 a + b + c = k 라고 할 때 a + b의 값을 갖는 배열을 만들기로 했다. a + b 배열을 만든 뒤 k..
* 개인 블로그에 작성한 내용을 복사해왔습니다. [Algorithm] BOJ 2251 BOJ 2251번 물통BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, 풀이를 하는 데 조금 시간이 걸렸습니다.처음에는 방문\_여부\[물통 A의 velog.io BOJ 2251번 물통 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net Intro BFS를 사용하여 풀이하였습니다. 다른 탐색 문제들에 비해 어떻게 풀이해야 할지 직관적으로 떠오르지 않아, ..
