NineTwo meet you

문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1 ×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1 ×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여 있고, 가구의 크기도 1 ×1이다. 로봇 청소기는 가구가 놓인 칸으로 이동할 수 없다. 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다. 방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오. 입력 입력은 여러 개의 테..

문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다. 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다..

문제 때는 2020년, 백준이는 월드 나라의 한 국민이다. 월드 나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라. 입력 첫 ..

문제 뱀과 사다리 게임을 즐겨 하는 큐브러버는 어느 날 궁금한 점이 생겼다. 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면, 최소 몇 번만에 도착점에 도착할 수 있을까? 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다. 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다. 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다. 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다. 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다. 뱀..

문제 깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다. 이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다. 사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다. 사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다. 시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다. 만약 도로 데이터가 만약 왼쪽의 그림과 같다면, 오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3..

문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 입력 첫째 줄에 별의 개수 n이 주어진다. (1 ≤ n ≤ 100) 둘째 줄부터 n개의 줄에 걸쳐 각 별의 x, y좌표가 실수 형태로 주어지며, 최대 소수점 둘째 자리까지 주어진다. 좌표는 1000을 넘지 않는 양의 실수이다. 출력 첫째 줄에 정답을 출력한다. 절대/상..

문제 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함선과 무역선들은 한 행성에서 다른 행성으로 무시할 수 있을 만큼 짧은 시간만에 이동할 수 있다. 하지만, 치안을 유지하기 위해서 플로우 내에 제국군을 주둔시켜야 한다. 모든 행성 간에 플로우를 설치하고 플로우 내에 제국군을 주둔하면, 제국의 제정이 악화되기 때문에 황제 윤석이는 제국의 모든 행성을 연결하면서 플로우 관리 비용을 최소한으로 하려 한다. N개의 행성은 정수 1,…, N으로 표시하고, 행성 i와 행성 j사이의 플로우 관리비용은 Cij이며, i = j인 경우 항상 0이다. 제국의 참모인 당신은 제국의 황..

프림 (Prim) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 하나의 시작점으로 구성된 트리에 간선을 하나씩 추가하는 방식 동작 과정 1. 그래프를 확인하고 출발 노드를 우선순위 큐에 저장한다. (start, 0) 이때 저장되는 가중치는 자기 자신이므로 0이다. 우선순위 큐 : (0, 0) 2. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 : (2, 1), (1, 5) 3. 우선순위 큐를 poll 했을 때 나온 노드와 이어진 노드를 가중치를 오름차순으로 정렬하는 우선순위 큐에 저장한다. 이때 한번 지나갔던 정점은 추가하지 않는다. 우선순위 큐 ..

크루스칼 (Kruskal) 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘 간선을 오름차순으로 정렬하고 이미 트리에 추가된 간선과 사이클을 이루지 않을 때 간선을 추가 간선이 사이클이 되지 않는지 확인하기 위해 유니온 파인드를 사용 동작 과정 1. 가중치가 오름차순으로 정렬된 우선순위 큐에 모든 간선을 추가한다. 우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치) : (0,1,1), (1,3,1), (2,3,2), (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5) 2. poll 한 값의 두 노드의 부모가 같은지 판단(사이클 여부 확인)..

벡터란? 유클리드 공간에서 방향과 크기를 포함하는 기하학적인 대상으로 보통 화살표로 표시한다. 벡터 표현 벡터를 표현할 때 점과 헷갈릴 수 있지만 점과 벡터는 엄현이 다른 것임을 알아야 한다. 단위 벡터 다양한 방향과 크기를 가진 벡터 중 크기가 1인 벡터를 모두 단위 벡터라고 칭한다. 크기가 1이 아닌 벡터를 크기가 1인 단위 벡터로 만드는 것을 정규화라고 칭한다. 표준 단위 벡터 / 기본 단위 벡터 크기가 1인 단위 벡터 중 i 번째 성분만 1이고 나머지는 0인 벡터를 표준 단위 벡터 또는 기본 단위 벡터라 칭한다. 모든 벡터는 표준 단위 벡터로 표현할 수 있다. 2차원의 표준 단위 벡터는 (1,0)과 (0,1)이고 3차원의 표준 단위 벡터는 (1,0,0), (0,1,0), (0,0,1)이다. (2,..