문제 https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 풀이 방법 한 자릿수 또는 두 자릿수로 끊어 공백을 만들고, 만들어진 수열의 길이가 N일 경우 출력하는 문제이다. 공백으로 분리한 수를 이미 사용했으면 더 진행하지 않고 멈추는 가지치기와 실행했던 과정을 되돌리는 백트래킹을 사용한다. 주의할 점은 성공 케이스에서 조건비교인데, 아래 코드처럼 수열의 개수로 해도 되고 다른 풀이처럼 만들어진 수열의 가장 큰 수로 비교해도 된다..
프로그래밍
문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 방법 (1,1)에서 (N,M)까지의 거리를 구하는 문제이다. 시작점과 도착점까지의 거리를 구하는 미로탐색과 비슷한 문제로, BFS로 해결할 수 있다. 다만 이 문제는 미로의 벽 하나를 부술 수 있다는게 차이점이다. 그렇다면 기존의 BFS 알고리즘에 벽을 부쉈는지, 안부쉈는지에 대해 추가로 처리해줘야 한다. 따라서 탐색 노드를 좌표뿐만 아니라 벽을 부쉈는지 안부쉈..
문제 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 풀이 방법 미로탈출 문제와 유사하지만 '불' 개념이 추가되어 시간이 지남에 따라 이동할 수 없는 지역이 추가되는 것이 차이점이다. 상근이가 바깥으로 나가는건 BFS로 풀 수 있고 마찬가지로 불도 상하좌우 한칸씩 움직이기 때문에 BFS로 갱신해주면 된다. 다만 새로운 노드 탐색을 할때 원래는 현재 방문 노드에서 인접한 노드들만을 탐색한다. 하지만 이 문제에서는 불이 전체적으로 퍼지기 때문에 이 탐색 과정을..
문제 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 풀이 방법 3차원 공간을 탐색해 시작지부터 목적지까지의 거리를 구하는 문제이다. 인접한 노드를 차례로 방문해 각 노드의 시작점까지의 거리를 구할 수 있는 BFS(너비 우선 탐색)을 사용해서 푼다. 탐색하면서 거리 배열을 갱신시켜주고, 탈출에 성공했을경우 목적지까지의 거리를 출력하면 된다. 코드 #include #include #include #include #include using namespa..
