![]()
문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 특정 시작점에서 다른 모든 정점으로 가는 최단 거리를 구해주는 알고리즘인 다익스트라를 이용하여 구현한다. 문제는 다른 모든 마을에서 파티가 열리는 마을로 가는 최단 거리와 돌아오는 최단 거리를 구해야 한다. - 각 마을로 돌아가는 최단 거리는 특정 시작점이 파티가 열리는 마을이므로 입력받은 대로 다익스트라를 적용하면 된다. - 그러나 모든 정점(각 마을)에..
문제링크 https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 코드 from collections import deque input = __import__('sys').stdin.readline n,m,r = map(int,input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a,b = map(int,inpu..
11725번: 트리의 부모 찾기 (acmicpc.net) 문제 풀이 입력이 길어 input이 아닌 sys모듈의 stdin.readline 사용 모든 노드의 연결구조를 봐야한다고 생각해서 dfs로 풀긴했지만, bfs로 푸는 것도 오답이 아니라고 생각함. 입력받기는 딕셔너리에 저장. 이때 정점 u와 v가 연결되어있다면 딕셔너리의 키값으로 둘 다 저장함. 이다음 깊이우선탐색을 하는데, 방문여부를 파악하는 동시에 답을 저장함. 이를 위해 딕셔너리 이용. 깊이우선이므로 스택(후입선출) 만들어서 루트노드인 1을 저장. 스택이 빌 때까지 while 반복. 스택에서 pop을 하며 그 노드를 node에 저장. 이 노드가 이미 방문된 노드라면 continue, 아니라면 방문했다는 의미로 visit에 저장. 루트노드인 1은..
![]()
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 문제 문제해석 데큐를 이용하여 순서를 나타내고 대기열 공간은 stack을 활용하여 순서대로 나갈 수 있는지 확인하는 문제이다. 코드 import collections N = int(input()) q = collections.deque(map(int, input().split())) tmp = list() min_value = 1 while q: if q[0] != min_value: tmp.a..
![]()
풀이 DFS를 활용하여 그림의 영역을 찾는다. 각각의 1로 이루어진 영역은 하나의 그림을 의미함. 따라서 DFS를 사용하여 연결된 1의 영역을 찾아내고, 각 그림의 넓이를 계산한다. FS 함수는 현재 위치 (x, y)에서 상하좌우로 탐색하며 연결된 영역을 찾아간다. 이때 주의해야 할 점은, 대각선으로는 연결되어 있지 않다고 하였으므로 상하좌우만 고려해야 한다. 만약 (x, y) 위치가 유효하고 아직 방문하지 않았으며, 값이 1이라면, 해당 위치를 방문한 것으로 표시하고 그림의 넓이를 1 증가시킨다. 그리고 이어서 인접한 위치들도 DFS를 호출하여 같은 그림에 속하는지 확인한다. 모든 위치를 순회하면서 그림의 개수와 가장 큰 그림의 넓이를 찾는다. 가장 큰 그림의 넓이를 출력한다. 코드 #include #..
![]()
문제 https://www.acmicpc.net/problem/1303 1303번: 전쟁 - 전투 첫째 줄에는 전쟁터의 가로 크기 N, 세로 크기 M(1 ≤ N, M ≤ 100)이 주어진다. 그 다음 두 번째 줄에서 M+1번째 줄에는 각각 (X, Y)에 있는 병사들의 옷색이 띄어쓰기 없이 주어진다. 모든 자리에는 www.acmicpc.net 풀이 - deque를 이용하여 BFS로 구현하였다. - 이중 반복문을 통해 탐색을 시작할 위치를 찾고, bfs를 호출한 결과의 제곱을 합한다. - bfs함수가 호출이 되면, 시작 위치를 방문했으므로 0으로 변경하고 q를 생성하여 시작 좌표를 append 하고 반복문을 통해 상하좌우를 확인한다. - 만약 상하좌우의 좌표가 범위를 벗어나지 않고 해당 위치의 병사가 시작 ..
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의 기본 구현문제입니다. 기본적으로는 dfs는 스택, bfs는 큐를 통해 구현하였습니다. 그리고 탐색 문제는 방문 여부를 판단하는 boolean 배열이 필요하므로, isVisit배열을 만들어 문제를 해결합니다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io..
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 1. 벽 세우기 -> make_wall 함수 : 재귀 호출 이용하여 0만날때 값을 1로 변경 -> count 증가 -> 밖으로 나올 때 다시 0으로 -> 벽 3개다 세우면 bfs호출 2. 바이러스 퍼뜨리기 & 안전영역 크기 재기-> dfs 함수 : 상하좌우 움직일 수 있게끔 d 변수 생성 - queue 만들어 map deepcopy -> 바이러스 퍼진 곳을 queue에 넣기. - 좌표값 확인하며 상..
![]()
Problem Solution 1. 테스트 케이스의 개수를 입력 받는다. 2. t번 반복하면서 아래 작업을 수행한다. - 각 테스트 케이스마다 두 개의 숫자 n과 m을 입력 받습니다. - m번만큼 무시하고 숫자 쌍을 입력 받습니다. - 각 테스트 케이스마다 n-1 값을 출력합니다.(이때, n은 입력된 값에서 1을 뺀 값) Answer #include using namespace std; int main(void) { int t; cin >> t; while(t--){ int n, m; cin >> n >> m; for (int i = 0; i > a >> b; } cout
https://www.acmicpc.net/problem/16637 정답 코드 import sys from collections import deque si = sys.stdin.readline N = int(si()) arr = list(map(str, si().rstrip())) answer = -sys.maxsize visited = [0 for i in range(N)] max_depth = ((N // 2) + 1) // 2 def calculate(first, second, arr): operator = arr[first + 1] first = int(arr[first]) second = int(arr[second]) if operator == '+': return str(first + sec..
![]()
문제 https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 게임 이론 문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. 입력 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) 출력 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을..
![]()
문제 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net Algorithm 모든 국가를 여행하기 위해 타야하는 비행기의 최소 갯수를 묻는 문제이다. 비행기의 최소갯수를 구하려면 각 지역을 1번씩만 방문하는게 당연히 최소가 될것이므로 이미 방문한 노드면 방문하지 않는 dfs를 사용하면 좋을것 같았다. 재귀를 이용하여 dfs를 구현하였고, 재귀가 호출될때마다 노드를 옮긴것이고, 즉 비행기를 탔다는 소리이므로 ans..
