본문 바로가기

🔅코딩테스트 공부🔅/❗백준138

[백준] 2468번 안전 영역(python) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 rain의 경우 1보다 적게 내리면 아무 지역도 잠기지 않는다. 1. 따라서 0부터 1씩 증가하며 map의 value가 잠길 경우 visit, maps를 모두 -1로 바꿔주었다. for i in range(n): for j in range(n): if maps[i][j] 2023. 2. 26.
[백준] 1865번 웜홀(python) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 1. 난이도 골드3 (🥇) 2. 문제해결 과정 인터넷에 있는 많은 글들이 dist[v] != INF을 검사하지 않으면 정답 처리 된다고 했다. 그러나 벨만포드에 대한 이해도가 부족한 나는 그 말이 도무지 😭이해 되지않아 백준 질문게시판 + 이 문제와 관련된 모든 글들을 정독했다. 문제 해결에 가장 큰 힌트가 된 글을 jh05013님이 백준 질문게시판에 올려주신 "풀이 및 논란 완전히 .. 2023. 2. 26.
[백준] 1956번 운동(python) https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 과정 (보완 필요해서 4번에 추가해놨음) 사이클을 이루는 도로를 찾기 위해서는 1. 플로이드 워셜 알고리즘을 이용해 모든 지점에서 다른 지점까지의 최단 경로를 구한다. 2. 출발 장소 -> 도착장소 , 도착장소 -> 출발장소로 가는 두 경로 모두 INF가 아닐 경우의 값 중 최솟값을 구한다. (cycle이 이뤄지지 않았을.. 2023. 2. 25.
[백준] 1238번 파티(python) 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 1. 난이도 골드3 (🥇) 2. 문제 해결 방법 우선 이 문제는 다익스트라로 풀면 되며, 학생은 n개로 구분된 마을에 한 명씩 살고있다는 조건이 있다. 예시를 보면 마을은 1,2,3,4,5번 5개가 있고, 파티의 장소는 2번이다. 따라서 아래와 같이 파티로 가는 길과 파티를 끝내고 집으로 돌아가는 길을 각각 다익스트라로 돌린 후 1,2,3,4,5번 중 가장 오래 걸린.. 2023. 2. 25.
[백준] 1389 케빈 베이컨의 6단계 법칙(python) https://www.acmicpc.net/problem/1389 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 BFS로도 해결가능하고 플로이드-워셜로도 해결 가능하지만 플로이드워셜을 활용해서 이 문제를 해결했다. 인접행렬을 양방향 리스트로 만들어주고, 친구를 거쳐서 도달한 횟수 중 최솟값을 인접행렬에 넣는다. 행렬의 각 행을 더한 후, 제일 작은 값의 index를 출력하면 된다. 3. 내가 작성한 코드 n,m = map(int, input().split()) #n 유저 m 친구관계 INF = int(1e9) graph = [[INF] * (n+1) for _ in range(n+1)] result = [] #케빈 베이컨 수 입력력 for i in range(1,n+1): for j in range(1.. 2023. 2. 24.
[백준] 5972번 택배 배송(python) https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 1. 난이도 골드5 (🥇) 2. 문제해결 방법 전형적인 다익스트라 문제이다. 다익스트라 알고리즘을 사용하고 distance의 마지막 위치를 return 해주면 된다. 3. 내가 작성한 코드 import heapq INF = int(1e9) n,m = map(int,input().split()) #n헛간 m소 graph = [[] for _ in range(n+1)] distance = [INF] * (n+.. 2023. 2. 24.
[백준] 11403번 경로 찾기(python) https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 플로이드 워셜 알고리즘을 이용하면 된다. 출발 -> 경유지까지 이어져 있고(True), 경유지->도착까지 이어져있으면(True) 출발-> 도착이 이어져있기 때문에 graph[출발][도착]에 1을 넣어주면 된다. 3. 내가 작성한 코드 n = int(input()) #정점 graph = [] for _ in range(n): graph.append(list(map(int, input().spl.. 2023. 2. 24.
[백준] 11404번 플로이드(python) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 문제의 이름에서 보이듯 이 문제는 플로이드 워셜 알고리즘을 사용해야 한다. 그러나 이 문제는 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다. 라는 함정이 있다. 테스트 케이스를 살펴보면 1 4 1 1 4 2 와 같이 1에서 4로 가는 노선이 두 개가 있는데, 뒤에 오는 값인 graph[1][4] = 2가 들어가게 되고, 이는 최단경로.. 2023. 2. 24.
[백준] 1504번 특정한 최단 경로(python) 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 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 다른 최단 경로 문제들과 다른 점은 1. 방향성이 없는 그래프이다(=양방향 모두 들릴 수 있다). 2. 두 정점을 반드시 거쳐야 한다. 1번은 graph에 append 할 때 for i in range(e): a,b,c = map(int, input().rstrip().split()) graph[a].ap.. 2023. 2. 24.

티스토리툴바