내 맴

문제 ) https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net [ 풀이 IDEA ] - 다익스트라(Dijkstra) 알고리즘을 이용해서 문제를 해결하였다. 다익스트라 알고리즘은 최소 힙(heapq) 이용해서 풀어주면 좋다는거!! 꼭 기억하자 1️⃣ 초기화 사항 => 시작점으로 부터의 거리 list(distance), heapq 정의 2️⃣ [시작 점(start) 👉 최소 힙에서 추출한 점(node) 👉 해당 점(node)와 연결된 다른 점(nnode)] 으로..

문제 ) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net [ 풀이 IDEA ] BFS이용해서 문제를 풀어줄 수 있다 1️⃣ BFS를 통해 열린 국경선을 체크한다. (조건: 두 나라의 인구 차이 L이상, R이하) 2️⃣ 국경이 열린 나라들의 위치를 list에 저장 3️⃣ 국경이 열린 나라들의 인구를 update 4️⃣ 국경이 열리지 않을 때까지 반복 - python code from collections import deque dx..

문제 ) https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net [ 풀이 IDEA ] 1. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이 2. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이 위의 2가지를 구해야한다. 2번 뿐만 아니라, 1번을 구할 때에도 문자열의 앞뒤가 같은 문자여야만 한다. 그렇기 때문에, 1/2번은 한번에 구해주면 된다! dictiona..

문제 ) https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net [ 풀이 IDEA ] 문제만 보면 단순해보이지만 그냥 BFS로만 풀다가는 시간오류가 난다 를 1턴으로 두고, 다음턴에 백조가 탐색 할 위치 큐 / 다음턴에 얼음이 녹을 위치 큐 를 따로 두고 BFS로 문제를 풀어야한다. 💡 문제 아이디어가 생각나지 않아서 다른분의 블로그를 참조해서 문제를 해결했다. https://itsmain.tistory.com/10 백준 ..

문제 ) https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net [ 풀이 IDEA ] 1. BFS/DFS로 풀어야하는 문제! 2. 그러나, 단순히 풀면 시간에러가 난다. 💡 SET 이용해서 문제 해결! ▶ BFS의 경우, queue대신에 set을 사용 & set에 좌표/visited(지나온 알파벳)을 저장한다 - python code dx = [0,0,-1,1] dy = [-1,1,0,0] def solution(board): global ma..

문제 ) https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net [ 풀이 IDEA ] 1. N, M ≤ 500,000 이므로 트램펄린을 한칸씩 옮기는 Brute Force로는 문제를 해결할 수가 없다! 2. 그러나, K

문제 ) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net [ 풀이 ] 그래프 탐색에 대한 문제이다. BFS, DFS 방법으로 둘 다 구현해 보았다. 먼저, DFS방법으로 푼 코드이다. 재귀함수를 이용해준다. - Python code (DFS ) visit=[1] def DFSWorm(current): global count, visit for i in range(1,n+1): # 바이러스에 걸리지 X & 길이 연결되어있는 경우 if i not i..

문제 ) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [ 풀이 ] BFS 와 DFS에 대한 문제이다. DFS와 BFS는 이진트리로 밖에 안해봤었는데 이 문제는 조금 달랐다 . DFS의 경우 , 만약 Node사이에 연결선이 존재한다면 연결된 Node부터 이어주게 된다. 그러나 BFS의 경우에는 level이 같은 Node들 부터 출력하게 된다. - DFS 설명 https://luz0911.tistory.co..