Jutudy

https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net [풀이] ​ DP로 풀면 되는 문제인데, O표시를 한 부분을 기준으로 생각하면 된다. ​ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 위의 배열에서 8번에 O 표시가 되어 있으므로 1번에서 8번까지 가는 경로의 수 ( A ) 와 8번에서 15번까지 가는 경로 ( B ) 를 구한 후 곱해주면 된다. ​ 총 경로의 수 = A * B [소스코드]..

https://www.acmicpc.net/problem/16959 16959번: 체스판 여행 1 크기가 N×N인 체스판이 있고, 체스판의 각 칸에는 1부터 N2까지의 정수가 한 번씩 적혀있다. 지학이는 이 체스판을 이용해서 재미있는 게임을 해보려고 한다. 지학이가 가지고 있는 말은 나이트, www.acmicpc.net [풀이] ​ BFS 문제이다. ​ 말은 1에서 시작해서 N^2-1 까지 차례대로 밟아가며 이동해야한다. ​ 차례대로 숫자가 1씩 늘어나면서 방문해야 하기 때문에 말은 현재 자신이 방문한 숫자 정보를 가지고 있어야 한다. ​ 중간에 다른 숫자가 적혀있는 부분도 거쳐갈 수 있기 때문에 자신이 다음에 방문해야 할 숫자가 아니면 원래 말이 가지고 있던 숫자 정보를 그대로 가지고 간다. ​ 현재 ..

https://www.acmicpc.net/problem/2188 2188번: 축사 배정 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해 www.acmicpc.net [풀이] 이분매칭의 기본적인 문제이다. A : 소 B : 축사 로 설정해서 A-B 에 해당하는 모든 간선을 그린 후, A 노드가 B 노드에 1:1 매칭될 수 있는 최대 매칭 수를 구한다. 기본적으로 dfs 개념을 숙지하고 dfs를 이용해서 풀어야한다. 처음으로 풀어 본 이분매칭 문제. [소스코드] import java.io.BufferedReader; import java.io.BufferedWrit..