mojo's Blog

13308번: 주유소 (acmicpc.net) 13308번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도 www.acmicpc.net 다익스트라 문제이다. 이 문제를 해결할 때 특히 최소 비용이 MAX_INT 값을 넘어간다는 것을 캐치하지 못해서 많이 삽질한 문제이다. 문제를 해결함에 있어서 int 로 설정해야 할지, long long 으로 설정해야 할지 미리 파악을 해두는 것이 중요하다. ※ 문제 접근 ① 어떠한 지점 P 에 대해서 특정 기름(oil) 으로 마지막 지점까지 도달하는데 최소 비용에 대한 배열 설계가 필요하다...

문제 링크 : 10775번: 공항 (acmicpc.net) 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 공항에 G 개의 게이트가 존재하며 1, 2, ..., G 의 번호를 가진다. 비행기는 P 개가 순서대로 도착하며 i 번째 비행기는 1 번부터 \(g_{i}\) 번까지의 게이트중 하나를 영구적으로 도킹할 수 있다고 한다. 도킹할 수 없다면 현재까지 도킹된 횟수를 출력하는 문제이다. 이 문제는 유니온 파인드 알고리즘을 활용하여 해결하였고 다음과 같이 이미지를 형상화하여 해결하..

문제 링크 : 24526번: 전화 돌리기 (acmicpc.net) 24526번: 전화 돌리기 첫 줄에 부원의 수 $N$과 관계의 수 $M$이 공백을 사이에 두고 정수로 주어진다. ($2 \le N \le 100,000$ , $1 \le M \le $ $500,000$) 둘째 줄부터 $M+1$번째 줄까지 어떤 부원 $U_{i}$가 전화를 받았을 때 다른 부원 www.acmicpc.net 사이클을 어떻게 처리해야 할지 고민을 했던 문제이다. 우선 방문배열을 2차원 배열 형태(visited[100001][2])로 선언하여 다음과 같이 처리하도록 하였다. visited[x][0] : 노드 x가 최초로 방문되었는지 판단하기 위한 용도이며 true로 마킹된 경우 방문한 경우다. visited[x][1] : DFS를..

문제 링크 : 1944번: 복제 로봇 (acmicpc.net) 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 최소 스패닝 트리 문제이다. 문제의 input 을 고려해서 어떻게 정답을 찾을지를 생각해보도록 하자. 5 2 11111 1S001 10001 1K1K1 11111 우선, 문제에서 요구한 것은 로봇의 시작지점인 S 부터 열쇠 K 를 모두 획득하는데 움직이는 횟수의 합을 최소로 하는 것이다. (2, 2) 에 있는 S 로 부터 시작하여 (2, 2) => (4, 2) => (4..

문제 링크 : 9370번: 미확인 도착지 (acmicpc.net) 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요..

문제 링크 : 3197번: 백조의 호수 (acmicpc.net) 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세..