1. 문제 출처 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 2. 풀이 BFS를 이용하지만 벽을 부수는 경우가 있기 때문에 데이크스트라 알고리즘도 같이 이용해야 한다. 벽부시는 것을 가중치로 두고 만약 벽을 부수지 않고 이동한다면, 가중치를 더해주지 않는 것이 필요하다. 다음과 같이 진행된다. 1. 상하좌우 중 범위를 나가지 않는 곳으로 이동 2. 해당 이동좌표에 벽이 있다면 전 가중치+1 을 해주고 append를 통..
1. 문제 출처 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 2. 풀이 데이크스트라를 1->v1->v2->n or 1->v2->v1->n 순으로 3번 사용해야 한다. 해당 해답은 pypy3 로 실행 하였다. import heapq #입력 n,e = map(int,input().split()) graph = [[] for _ in range(n+1)] # 입력 for _ in range(e): a,..
1. 문제 출처 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 2. 풀이 각 노드를 시작점으로 경로를 구해줘야 한다. import heapq # 입력 n,m,x = map(int, input().split()) graph = [[] for _ in range(n+1)] distance = [[float('inf')] * (n+1) for _ in range(n+1)] # 입력 for _ in range(m): s..
1. 문제 출처 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2. 풀이 데이크스트라 알고리즘을 이용한 문제이다... 여기서 주의 할점은 그래프 배열의 사이즈를 max(n,k)로 하는 것이아니라 100000로 해야한다. 왜냐하면 max 를 사용해서 지정 할경우 해당 범위를 지나서 도착하는 것이 더빠를 수 있는데 그것을 계산하지 못하기 때문이다. import heapq #입력 n,k = map(int, inpu..
1. 문제 출처 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 풀이 단순 데이크스트라 알고리즘을 이용하는 문제이다. import sys input = sys.stdin.readline import heapq # 최대값 정의 INF = float('inf') # 입력 n = int(input()) m = int(input()) # 그래프와 거리 초기화 graph = [[] for _ in range(n+1..
1. 문제 출처 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 풀이 데이크스트라를 사용하는 문제이다. 데이크스트라 알고리즘은 별로 사용한 적이 없어서 많이 해멘던 것 같다. 그래프 자료 구조를 사용하여 weights ,node, edge 를 구현 하였고 해당 구조를 사용하여 데이크스트라 알고리즘 을 사용하기 위해 우선순위큐를 구현해야 했다. 이 우선순위 큐를 구현하기 위해 heap 구조를 사용하였다...
1. 문제 출처 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2. 풀이 DFS 와 BFS 에 대한 기초적인 문제를 확인 할 수 있었다. # 필요 라이브러리 불러오가 import copy from collections import deque # 입력 n, m, v = map(int, input().split()) # 그래프 값 초기화 graph = [[0 for _ in range(n)] for _ in ..
1. 문제 출처 https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 2. 풀이 단순 구현 문제이다 # 입력 n = int(input()) strings = [] for _ in range(n): strings.append(input()) def solution(): # 결과값 result = 0 # 문자열 하나씩 확인 for string in strings: flag = True # 각 문자 c = string[0..
