https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹 문제다. 스도쿠를 완성시키면 되는 문제인데 이와 유사한 문제로 2580 스도쿠 문제가 있다. 두 문제의 차이점은 입력에서 공백의 유무가 전부다. 2580 문제를 전에 푼 적이 있어서 그 코드를 넣었더니 맞았다. https://abbiddo.tistory.com/59 웃긴 점은 제한에 저렇게 쓰여져 있어 들어가봤더니 2580문제에 대한 답이 있다. 넣어보니 진짜 맞는다. 근데 내가 푼..
DFS
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net DFS 문제다. BFS를 풀려고 BFS 문제집에서 찾은 문젠데 DFS여서 뻘짓했다^!^ 알파벳을 지나가면서 같은 알파벳을 또 밟을 수는 없는 문제이므로 방문 배열을 해당 알파벳을 밟았는지 확인하는데 사용했다. 고로 방문 배열은 26칸으로 선언했다. #include #include using namespace std; // 상하좌우 탐색을 위함 int dr[4] = { -1, 0, 1, 0 ..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 트리와 DFS 문제다. 입력으로 받은 부모 노드의 정보를 이용해 루트 노드의 번호를 저장한다. -1 이외의 값이 들어오면 부모와 자식의 노드를 저장하는데 부모는 유일하기 때문에 부모 노드를 인덱스로 이용했다. 지울 노드의 번호를 입력 받고 지울 노드가 루트 노트라면 0을 출력 후 바로 종료한다. 단말 노드의 개수를 카운트 하기 위해서는 DFS를 이용한다. 방문 검사 후 단말 노드거나, 자식 ..
