https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 문자열과 백트래킹 문제다. 모든 언어는 "anti"로 시작되고, "tica"로 끝난다. 모든 언어는 8글자 이상이고 15글자 이하다. 학생들은 K개의 글자로만 이루어진 단어만 읽을 수 있다. 즉, K개에 a, n, t, i, c은 필수로 포함된다. a, n, t, i, c는 항상 포함되므로 별도로 확인할 필요가 없기 때문에 문자열을 입력 받을 때 앞뒤 고정 부분을 제거하고 저장한다. K가 ..
Algorithm/DFS
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문제에 대한 답이 있다. 넣어보니 진짜 맞는다. 근데 내가 푼..
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹 문제다. 9 x 9로 배열이 크지 않아 백트래킹을 이용했다. 배열에서 0인 칸을 따로 저장해두고 해당 칸을 순차적으로 채워나가는 방식이다. 채울 때의 조건은 같은 행이나 열에 그 숫자가 없고 3 x 3 칸 안에 그 숫자가 없어야 한다. 스도쿠가 다 채워지면 해당 스도쿠 답을 출력한다. #include #include using namespace std; bool complete; int ..
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 브루트포스와 백트래킹 문제다. 1. m개의 치킨 집 선택 2. 각 집에서 치킨 집의 가장 가까운 거리를 구하고 모든 집에서의 거리 합 구하기 3. 모든 조합의 경우에서 2번을 수행해 최소 거리 구하기 로 방법을 생각했다. m개의 치킨 집을 선택하기 위해서는 재귀 백트래킹을 사용했다. 집과 치킨 집의 거리를 구하기 위해서는 좌표 계산을 했다. 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를 이용한다. 방문 검사 후 단말 노드거나, 자식 ..
