어흥

문제 링크: https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 www.acmicpc.net 1. 주의할 점 - 다익스트라를 통해 구현가능하다. - 우선순위큐를 사용하여 이미 현 위치의 Node에서 출발한 적이..

문제 링크: https://www.acmicpc.net/problem/15558 15558번: 점프 게임 첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보가 주어지고, 각 문자의 의미는 왼쪽 줄의 의미와 동일하다. 왼쪽 줄의 1번 칸은 항상 안전한 칸이다. www.acmicpc.net 1. 주의할 점 - 현 자리에서 이동을 했을 때 N-1칸보다 높게 갈 수 있다면 끝난다 - 사라질 예정인 줄로 가지 않도록 한다 2. 구현 - BFS를 통해 구현하며, 현 위치를 Check[0][idx]라고 하면, Check[0][idx-1], Check[0]..

문제 링크: https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 서있 www.acmicpc.net 문제 링크: https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 문제 창영과 상근은 ..

문제 링크: https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. 주의할 점 - BFS를 잘못 사용할 경우 시간초과가 발생한다 - K의 값이 0~10이므로 Check[1000][1000][11]로 설정해야 한다 -> 11 대신 10을 사용할 경우 틀린다 - 낮의 경우에만 벽을 부술 수 있다 2. 구현 - 벽 부수고 이동하기 1이나 2와 비슷한 방법을 사용하지만, 낮과 밤의 구분을 추가한다 - 낮일 경우(Sun..

문제 링크: https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. 주의할 점 - K의 값이 0~10이므로 방문 배열 Check[1000][1000][11]로 설정한다 - 출발지점도 포함이다 2. 구현 - 구조체를 이용하여 X좌표, Y좌표, 벽을 부순 횟수를 저장하는 Queue를 통해 BFS 탐색을 한다 - 4방향을 탐색하며, 벽이 아닌 경우 현재 벽을 부순 횟수로 이동하려는 지점을 방문한 적이 없다면 Queu..

문제 링크: https://www.acmicpc.net/problem/5213 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단 www.acmicpc.net 1. 주의할 점 - 타일 1개에는 2개의 원소가 포함된다 - N의 범위가 500이하이므로 최대범위는 501까지로 설정한다 ->..

문제 링크: https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 주의할 점 - Node의 최대가 10만개다 -> Vector를 사용한다 - Root Node는 1이다 2. 구현 - BFS를 통해 구한다 - Queue에 1을 넣고 시작한다 - Queue에서 Pop한 원소에 맞닿아있는 다른 Node들이 방문하지 않은 상태라면 해당 Node들의 부모를 현재 Pop한 Node로 설정한 후, 큐에 추가한다 - 위의 과정을 모든 Node에 방문할 때 까지 진행한다. #include #include #include u..

문제 링크: https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 1. 주의할 점 - DFS를 통해 10번이상 실행하지 않도록 설계한다. - 구슬이 겹쳐지는 경우 따로 처리한다 2...