BOJ

    BOJ 2580 · 스도쿠

    알고리즘 분류 : 백트래킹 스도쿠는 9 x 9 칸에 숫자를 채워 넣는 퍼즐 게임이다. 워낙 유명한 게임이니, 부연 설명은 생략. 이 문제는 비워진 칸에 숫자를 채워 넣어야 한다. N-퀸과 마찬가지로 백트래킹 알고리즘을 쓰면 된다. 가로 줄, 세로 줄, 서브 사각형을 체크할 변수를 각각 2차원 배열로 선언한다.row는 가로 줄(행)을 나타내며, 인덱스는 [행 번호] [채워 넣은 숫자] 이다.col은 세로 줄(열)을 나타내며, 인덱스는 [열 번호] [채워 넣은 숫자] 이다.squ는 3 x 3 사이즈의 서브 사각형을 나타내며, 인덱스는 [서브 사각형 번호] [채워 넣은 숫자] 이다.서브 사각형은 왼쪽 위에서부터 오른쪽 아래까지 0~8로 번호를 매긴다.1칸의 인덱스를 (X, Y)로 나타낸다고 할 때, 3 x 3..

    BOJ 9663 · N-Queen

    알고리즘 분류 : 백트래킹 N-퀸은 백트래킹 알고리즘에서 가장 대표적인 문제다. N x N 사이즈의 체스판에 N개의 퀸을 놓는 방법의 수를 구해야 한다.다음 위치에 퀸을 놓을 때마다, 해당 위치에 퀸을 놓을 수 있는지 확인하면서 백트래킹을 하면 된다. 가능 여부를 확인할 때, 하나의 배열에서 매번 상하좌우 대각선을 확인하는 것은 효율적이지 않다.3개의 배열을 만들고, 각각 세로 줄(|), 대각선 줄(/), 대각선 줄(\)을 체크한다.N x N 판에서 한 칸의 인덱스를 [X, Y]라 하자. 세로 줄(|)은 각 칸이 [Y]이며, 대각선(/)은 각 칸이 [X+Y]이고, 대각선(\)은 각 칸이 [X-Y+N-1]이다. 아래의 그림은 N이 5일 때의 예시다.solve 함수에서 인자 i는 행(row)이며, for 문..

    BOJ 1987 · 알파벳

    알고리즘 분류 : DFS, 백트래킹 N x M 사이즈의 보드에서 (0, 0) 부터 출발하여 최대한 많이 지날 수 있는 거리를 구하는 문제다. 단, 이동할 때 이미 지나쳤던 알파벳을 다시 지날 수 없다. DFS 기반에 백트래킹을 하면 된다. 방문 여부를 체크할 check 배열의 길이는 알파벳의 개수(26개) 만큼 선언한다.상하좌우로 이동하면서, 방문하지 않은 알파벳이라면 true로 체크한다.이동하면서, 이미 방문한 알파벳이라면 무시한다.DFS이므로, 가장 깊게 들어갔을 때가 정답이 된다. C++ 소스코드 #include int n, m, ans; char a[20][20]; bool check[26]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; void..

    BOJ 1248 · 맞춰봐

    알고리즘 분류 : 백트래킹 입력으로 주어지는 합의 부호에 맞는 숫자 배열을 출력하는 문제다. 총 21개의 숫자 중에서 N개의 숫자를 골라야 한다. 일반적인 재귀 함수를 통해 브루트 포스로 구현하면 시간 초과가 나기 쉬우므로, 백트래킹 기법을 사용해야 한다. 숫자의 범위 (-10 ~ 10) 만큼 재귀 함수를 호출한다.하나의 숫자를 고를 때마다, 이 숫자가 주어진 부호에 맞는지 확인한다.해당 숫자가 가능하다면, 다음 재귀 함수를 호출한다.하나의 숫자 리스트만 찾으면 되므로, 찾으면 바로 프로그램을 종료한다. C++ 소스코드 #include #include #include using namespace std; int n; char a[10][10]; vector v; bool possible(int idx) ..

    BOJ 6087 · 레이저 통신

    알고리즘 분류 : BFS 'C'와 'C' 사이를 레이저로 연결하기 위해 필요한 거울의 개수를 세는 문제다. 최소의 거울을 설치해야 하므로, BFS 탐색을 통해 해결하는 것이 좋다. 레이저는 직선으로 움직이며, 레이저가 방향을 꺾기 위해서 거울이 필요하다. 기본적으로 BFS 탐색을 하되, 한 번 이동할 때 갈 수 있는 데까지 이동한다."갈 수 있는 데까지"란, 벽('*')을 만나기 전까지 또는 범위를 벗어나기 전까지이다.같은 방향으로 한 칸씩 이동할 때마다, 같은 이동 거리로 저장한다.같은 방향으로 갈 수 있는 데까지는 모두 방문 체크를 했으므로, 다른 방향으로 가는 곳은 이동 거리 +1을 해주면 된다. C++ 소스코드 #include #include using namespace std; struct la..

    BOJ 1445 · 일요일 아침의 데이트

    알고리즘 분류 : 다익스트라 S부터 출발해서 F에 도착할 때까지, 쓰레기를 최소로 지나면서, 쓰레기의 옆을 최소로 지나는 방법을 찾는 문제다. 두 가지의 우선순위 조건 때문에, 다익스트라 알고리즘을 사용하는 것이 좋다. 다익스트라를 이용하기 위해, 입력으로 주어지는 문자열 맵에 상응하는 인접 행렬을 만든다.쓰레기가 있는 칸 'g'는 2500으로 두고, g에 인접한 4칸은 1로 둔다. 나머지 칸은 0으로 둔다.맵이 최대 50*50으로 주어지기 때문에, 쓰레기 칸('g')에 넉넉하게 큰 값을 주는 것이 좋다. 예를 들어, 쓰레기 칸에 3을 주면 쓰레기 옆 칸을 3번 이동한 것과 구분할 수 없기 때문이다.정답은 dist 배열에 있으며, 2500으로 나눈 몫이 쓰레기를 지난 횟수이며, 2500으로 나눈 나머지가..

    BOJ 2665 · 미로만들기

    알고리즘 분류 : BFS 미로를 이동하면서 검은 방을 흰 방으로 만드는 최소 횟수를 구해야 하는 문제다. 덱(Deque)과 BFS를 이용하여 해결할 수 있다. 이 문제는 BOJ 1261 '알고스팟' 문제와 유사하다. 흰 방을 이동할 때는 덱의 뒤에 넣고, 이동 거리는 이전과 같게 한다.검은 방을 이동할 때는 덱의 앞에 넣고, 이동 거리를 +1 업데이트한다.덱에서 이동 좌표를 꺼낼 때, 덱의 뒤에서부터 꺼낸다. C++ 소스코드 #include #include using namespace std; struct maze { int x, y; }; int n; int a[50][50]; int dist[50][50]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}..

    BOJ 2529 · 부등호

    알고리즘 분류 : 백트래킹 기본적으로 재귀 함수를 이용하여 브루트 포스로 구현할 수 있다. 재귀 함수를 호출하기 전에 부등호 체크를 하는 방식으로 백트래킹을 하여 시간을 단축할 수 있다. 하나의 숫자를 구하기 위해서 입력으로 주어진 길이(N)+1 만큼 재귀 함수를 호출해야 한다. 올바른 부등식은 숫자 개수가 부등호 개수보다 1개 더 많다.재귀 함수 종료 조건 : 숫자 개수(길이) == N+1수를 중복하여 사용할 수 없으므로, check 배열을 별도로 만들어서 사용 여부를 확인해야 한다.재귀 함수를 호출하기 전에, 다음 숫자가 부등식에 맞는지 살펴봐야 한다.예를 들어, 주어진 부등호가 > 라면, 0 2 > 1은 가능하다. 하지만 3 1 > 0은 불가능하다. 이런 경우, 3 < ..