개발조아

문제 링크 : https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 처음에는 문제의 조건이 좀 어려웠었다. 하지만 결국 최소한의 비용으로 최소한의 개수로 연결해라인데 결국 다익스트라를 사용하면 된다. 다익스트라로 각 점마다의 최단경로를 구할 수 있다. 하지만 경로를 저장해야한다. 그래서 나는 비용과 연결된 이전 노드를 저장했다. 2번 노드에서 3번노드로 연결되어있고 비용이 1이라면 배열[3] = (2,1) 이런식으로 저장된..

문제 링크 : https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 기본적인 다익스트라 문제이다. 우선순위 큐를 이용하여 잃은 금액이 최소인 것을 우선적으로 빼서 진행하면 된다. from sys import stdin from heapq import heappush, heappop input = stdin.readline dx = [-1,1,0,0] dy = [0,0,-1,1] INF = 9876543210 def solv(): p..

문제 링크 : https://www.acmicpc.net/problem/16509 16509번: 장군 오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 호근이를 위해 www.acmicpc.net 이동 규칙이 특이한 BFS 문제이다. 문제에 왕에 대한 규칙이 있지만 무시해도된다. 현재 점에서 상하좌우로 한칸 간후 해당 칸에서 대각으로 두칸을 이동한것이 한번의 움직임이다. 파란점이 상이 움직일 수 있는 구역이다. 그리고 움직이는 도중에 다른 말을 만나면 안된다. 왕도 해당 된다. 그리고 움직임의 끝에 왕과 만나야한다. 다시말해 위의 그림에 파란점에 왕이 있어야 만나는 것이다. 위에 그림..

문제 링크 : https://www.acmicpc.net/problem/9519 9519번: 졸려 첫째 줄에 X(1 ≤ X ≤ 1,000,000,000) 가 주어지고, 둘째 줄에 X번 깜박인 후의 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 구간 [3,1000]에 포함된다. www.acmicpc.net X가 10억까지여서 규칙을 찾아서 하려고 했던 문제이다. 10번 돌리기에는 너무 많으니까 다시 시작 문자열로 돌아오는 섞는 횟수를 규칙으로 찾으려고 했는데 규칙이 없는 것같아서 포기했다. 그래서 그냥 반복문으로 구했다. 다시 시작 문자열로 돌아올때까지 문자를 섞고, 중간에 생성된 문자열을 배열에 추가했다. 예제 1번의 입력이 주어진다면 배열은 아래 순서대로 들어갈 것이다. acefdb..

문제 링크 : https://www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 별다른 어려운 조건이나 규칙이 없어서 주어진 조건대로 구현만 하면 된다. 우선 종수의 위치를 따로 저장하고., 미친 아두이노의 위치는 큐에 담는다. 그리고 맵을 조금 변경했다. 빈칸은 0, 종수는 -1, 미친 아두이노는 1로 초기화를 시작하고 했다. 1 이상의 숫자는 해당 점에 미친 아두이노의 개수를 나타낸다. 알고리즘의 순서는 다음과 같다. 1. 종수 이동 만약 미친 아두이노랑 ..

문제 링크 : https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 바로 전에 풀이한 배열에서 이동과 아주 유사하다. https://westmino.tistory.com/69 [BOJ/백준] 1981 배열에서 이동 파이썬 문제 링크 : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 ..

문제 링크 : https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 접근법을 모르겠어서 알고리즘을 찾아보고 푼 문제이다. 핵심은 투포인터를 이용하는 것이다. 배열의 숫자 리스트를 정렬해서 따로 만들고 투포인터로 최소, 최대값을 결정하고 BFS 실행 후 조정해간다. BFS를 실행할때 시작점과 그리고 중간에 들르는 점들에 대해서 이전에 정한 최소, 최대값 범위에 포함되는지 체크해야한다. 모든 점이 범위를 통과하고 목표점에 도달했다..

문제 링크 : https://www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net 문제는 그냥 BFS 문제이다. 두 로봇이 통신하기 위해선 이웃한 두점으로 로봇이 이동해야한다. 이때 드는 비용의 최솟값을 구해야한다. 한가지 주의할 점은 두 로봇이 같은 위치에 있을 수 있다는 것이다. 이부분을 체크해줘야한다. 처음에는 BFS를 두번 돌렸다. 그래서 한 로봇에서 BFS를 돌리면서 각 점까지의 최소값을 저장했다. 그리고 다른 로봇에서 BFS를 돌..