https://www.acmicpc.net/problem/17825처음에는 시작 칸에 말 4개가 있다.말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.말이 이동을 마칠 때마다 칸에..

https://www.acmicpc.net/problem/1799 N-Queen하고 사실상 똑같은 문제라고 생각한다.N-Queen에서는 퀸이 한 열에 한개밖에 못놓는 것을 기준으로 재귀를 돌렸다.비숍은 한 열에는 여러개가 올 수 있고 각 대각선에 한개씩 밖에 못오기 때문에 대각선을 기준으로 재귀를 돌리면 된다. 우상향 대각선을 기준으로 재귀를 돌렸고 어느 대각선을 기준으로 잡는지는 당연히 상관이 없다.그림으로 보면 다음과 같이 탐색했다.특정 칸에 도착했을 때 그 칸이 비숍이 놓을 수 있는 자리이고 화살표 방향과 수직인 대각선상에 다른 비숍이 없다면 비숍을 놓으면서 탐색해나가면 된다. 대각선을 구분하는 방법은 N-Queen포스팅 때 했지만 저 2n-1개의 대각선을 각각 인덱싱한다.대각선으로 해당하는 모든 ..

https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 백트래킹을 이용하는 문제이다. 재귀함수의 작동원리를 완벽하게 알지 못하다면 디버깅을 통해서 한번 코드가 어떻게 작동되는지 확인하면 좋을거 같다. 백트래킹의 좋은 예시로 미로가 있는데, 길을 찾다가 막다른 길이 나오면 다시 갈림길로 돌아가서 다른 방향으로 가야한다. 그때 다시 갈림길로 돌아가는 것을 백트래킹과정이라고 하면 이해하기 쉽다. 문제의 경우에는 친구의 연결관계를 찾다가 5명이 연결되기 전에 끊기면 끊기기 한단계 전 친구로 돌아가서 끊기는 쪽말고 다른 친구와 연결해봐야하는데 이 과정이 백트래킹 과..