2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 주의해야 할 점 * 벽을 부쉈지만 최단경로가 아닌 경로와, 벽을 부수지 않는 최단 경로에서 경로가 서로 겹칠 경우, 제대로된 최단 경로를 구할 수 없게 된다. 이를 꼭 신경써주어야 한다. 해당 문제는 bfs를 사용하지만, 큐에 넣을 요소들이 더 추가되었고, 방문 내역을 저장하는 visit 배열이 true false 가 아니라, int 형으로 선언을 해서 해당 노드가 벽을 부순 경로에 포함되는지, 벽을 부수지 않아본 경로에 포함되는지 ..
15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 www.acmicpc.net 처음에는 2차원 배열형태로 값이 주어져서 당연히 dfs나 bfs로 푸는 문제인줄 알았으나, 이 문제는 조합 알고리즘으로 푸는 문제였다. 조합 알고리즘만 있다면 매우 간단하게 구할 수 있다. 로직을 간단..
2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 일단 LIS (가장 긴 증가하는 부분 수열) 의 응용문제이다. 따라서 LIS를 이용해서 풀면 쉽게 풀린다. 전깃줄이 이어져있는 전봇대 A-B 가 주어지면, 전봇대 A 의 위치대로 오름차순으로 정렬을 해준다. 이 때, 전깃줄이 서로 겹치지 않기 위해서는 전봇대 A가 소팅 되었을 때 1-1 2-2 3-3 ... N-N 이렇게 전봇대 B 역시 오름차..
11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이 문제를 풀기전에 먼저 '가장 긴 증가하는 부분 수열' 문제를 풀기를 권장한다! 왜냐하면 해당 문제를 응용해서 푸는 문제이기 때문이다. S1 Sk+1 > ... SN-1 > SN 이렇게 생긴 수열을 바이토닉 수열이라고 한다. 여기서 보이는 규칙은 Sk 값을 기준으로 왼쪽은 '증가하는 부분 수열' 이고 오른쪽은 '감소하는 부분 수열' 이라는 점이다. 그렇다! Sk 값의 가장 긴 바이토닉 부분 수열은 결국 0부터 Sk까지의 가장 긴 증가하는 부..