FandPROG FandPROG

문제 설명문제에서 주어진 고리분지는 N × M 크기의 격자로, 초원, 빙판, 산으로 이루어져 있다. 늑대는 산을 제외한 칸으로 이동하며, 빙판에서는 초원이나 산에 부딪칠 때까지 미끄러진다. 이때 지도에서 늑대가 도달할 수 없는 초원인 칸들을 '안전한 곳'으로 표시하는 프로그램을 작성하시오. (3 ≤ N, M ≤ 100) N, M범위가 작음으로, 전체탐색으로 충분히 풀리는 문제라는 것을 알 수 있다. 얼음에서의 이동을 구현하기 위해 queue에 3개의 변수를 구조체로 잡아 사용했다. 현재 좌표값 x, y와 전칸에서 현재 칸으로 넘어올때의 방향을 이용해 queue를 잡고 얼음이라면 전에서의 방향대로 계속 움직이게끔 구현하였다.1. 현재칸이 얼음이라면     - 가야하는 방향에 산이있다면 : 4방검사를 진행한..

문제 설명종우는 모든 지점을 거치되, 같은 구간을 두 번 이상 지나지 않는 퍼레이드 경로를 구성하려 한다. 이를 위해 주어진 그래프에서 종우가 원하는 경로를 찾을 수 있는지의 여부를 구하는 문제이다.(V, E ≤ 3,000) 이 문제는 한붓그리기 문제라는 것을 알 수 있다. 한붓그리기 즉 오일러 사이클이나 오일러 트레일이 존재하는지를 판단하면 된다.오일러 사이클 = 모든 정점에서의 간선의 개수가 짝수.오일러 트레일 = 두 정점에서의 간선의 개수만 홀수(나머지 정점은 모두 짝수여야함).즉, 모든 정점에서 연결된 간선의 수를 각각 세어 홀수인 지점이 없거나 2개인 경우 해당 조건을 만족한다.※해당 문제에서 모든 정점이 연결 되어있다는 보장을 하지 않았음으로, 유니온 파인드를 통해 주어진 그래프가 하나의 컴포..

문제 설명RGB 거리에는 집이 여러 채 있고, 각 집을 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다. 각각의 집을 칠하는 비용이 주어지며, 인접한 두 집이 같은 색이 되지 않도록 하면서 모든 집을 칠하는 데 드는 최소 비용을(n ≤ 1,000)구하는 문제이다.  인접한 두 집이 서로 같은 색이 되지 않도록 칠해야 함에 주의하자. Dp[i][j] = "i번째집을 j색으로 칠할때 드는 최소비용"으로 정의 한다면 점화식은 다음과 같다. dp[i][k] = min(dp[i][k], dp[i-1][j] + arr[i][k])i번째 집을 색 k로 칠할 때의 최소 비용은 i-1번째 집을 j 색으로 칠한 비용에 i번째 집을 k 색으로 칠하는 비용을 더한 값 중 최소값으로 갱신한다.단, j와 k가 ..

문제 설명몇칸이 비어있는 9x9 격자판이 주어졌을 때 해당 스도쿠를 채워 출력하는 문제.  이 문제는 백트래킹을 사용하여 빈칸을 채워 스도쿠 퍼즐을 해결 할 수 있다. 각 행(row), 각 열(column)에 대해 숫자가 사용되었는지를 체크해주다. 또, 각 3x3 서브그리드에 대해 숫자가 사용되었는지도 체크해주어야한다. 다음 3가지를 각각 체크하며 비어있는 칸을 백트래킹을 이용하여 풀면 된다.소스코드더보기#include #include #include using namespace std;int chs[10][10], chg[10][10];int chsq[10][10];int m_sq[10][10];int ch = 0;vector > emp;int sqnumjudge(int x, int y){ if (0 ..

문제 설명N-Queen 문제는 N × N 체스판 위에 N개의 퀸을 서로 공격하지 못하게 배치하는 방법의 수를 구하는 문제이다. (이때 1 ≤ N ≤ 15)  N-Queen문제는 N범위가 작기 때문에 충분히 백트래킹을 통해 풀 수 있다. 하지만 퀸을 놓을 때 마다 상, 하, 좌, 우, 대각선 2방향을 모두 검사하려면 시간이 방대하게 걸린다. 따라서 이를 한번에 체크를 통해 확인해주어야 한다. 간단하게 현재 탐색중인 행 또는 열을 재귀함수의 인자로 하고, 체크배열 3개를 통해 대각성, 열을 체크해가며 탐색하면된다.-기저 사례: 현재 탐색중인 행(row)이 N보다 크거나 같다면, 모든 퀸을 성공적으로 배치한 것이므로 cnt를 1 증가시킨다.-백트래킹 과정- 행(row) x에서 가능한 모든 열(column) i..

문제 설명2차원 좌표가 n개 주어졌을 때 이를 이용해만들 수 있는 직사각형의 개수를 구하는 문제.(이때 1 ≤ n ≤ 5,000) n범위가 5,000으로 작기 때문에 O(n * nlongn)의 방법으로도 풀 수 있다. 주어진 모든 점으로 만들 수 있는 모든 대각선에 대해 set자료구조를 통해 나머지 두 점의 존재유무를 확인하면 되는 간단한 문제이다.소스코드더보기#include #include #include #include using namespace std;int n;vector > vec;set > st;int main(){ int i, j; scanf("%d", &n); for(i=0;i

문제 설명  여러 회의의 시작시간과 끝나는 시간이 주어졌을 때, 최대 사용할 수 있는 회의의 최대 개수를 출력한다. (총 회의의 수 ≤ 100,000)  이 문제는 그리디 알고리즘을 이용하여 풀 수 있다. 회의들의 시작 시간과 종료 시간을 바탕으로 최대한 많은 회의를 진행할 수있게 하려면 끝나는 시간을 기준으로 정렬하는 것이 좋다. 이를 알기 위해서는 입출력 예를 수직선에 그려보는 것이 좋다. 입력 예111 43 50 65 73 85 96 108 118 122 1312 14를 수직선상에 나타내면더보기0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |----|   |----| |------|       |----|   |--------|       |------|         |------..

최종 순위 문제 https://www.acmicpc.net/problem/3665 원래 등수와 서로 바뀐 등수가 출력 되었을 때의 새로운 등수를 출력하는 문제이다. 만약 확실하지않다면 "?" , 데이터의 일관성이 없어 오류가 발생하는 경우에는 "IMPOSSIBLE"을 출력한다. 입출력 형식 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500) n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다. 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000) 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이..