1. 백트래킹을 이용한 N-QUEEN 문제 (백준 9663번)

2.백트랙킹을 이용한 풀이

4X4 체스판에서의 예를 들어보면 처음에 nQueen(iArr,4,0) 이라는 함수를 호출한다. 이 함수의 뜻은 1번째 행에 퀸을 놓는다 라는 뜻이다. 함수 속에 들어가게 되면 1번째 행에는 퀸을 1,2,3,4 열에 퀸을 놓을 수 있다. 이것을 각각의 경우로 따지기 위해 for문의 인덱스를 0<=i<N 이라는 값으로 셋팅 해준것이다. 그리고 iArr[0]=0 이 들어가게 된다. 이 뜻은 1번째 행의 1번째 열에 퀸을 놓겠다 라는 뜻이다. 그런다음 조건문안에 promising(iArr,4,0) 이라는 함수를 호출하게 된다. 이 함수 안에 들어가게 되면 지금 행의 이전까지의 퀸을 놓은 경우에 따라 지금 놓은 퀸의 위치가 유효한가를 따져보는 함수이다. 하지만 row가 0이므로 이전의 놓은 값은 아무것도 없기에(i<0) for문 자체를 돌지 않으므로 return 값은 true가 되어 퀸을 놓을 수 있게 된다. 여기서 promising 함수안의 조건문을 보면 iArr[row]==iArr[i] || row-i==Math.abs(iArr[row]-iArr[i]) 이라는 조건이 있다.

이 조건은 퀸의 성질을 나타낸 것인데 퀸은 자신이 놓인 곳에서 행,열, 대각선 아무 곳이나 이동하여 공격 할수 있다라는 성질을 이용해 만약 이전에 놓였던

퀸들의 위치에서 행,열,대각선 위치와 지금 놓은 퀸의 위치가 같다면 false를 리턴하라는 조건문이다. 이렇게 row를 하나씩 증가시켜가며 퀸을 놓는 것이다.

만약 promising이 false라면 다음 퀸을 놓지 않고 for문으로 다시 돌아가 i를 1 증가시켜 다음 위치에 퀸을 놓았을때를 비교 한다.(백트랙킹) 만약 해당 열에

어느곳에도 놓을수 없다면 이전 퀸으로 돌아가 이전 퀸의 위치를 i+1로 변경해서 다시 퀸을 놓는 경우의 수를 따져보는 것이다.(백트랙킹)

입력:

8

출력:

92

1.백트랙킹- 로또문제(백준6603번)

2. 백트랙킹을 이용한 풀이

예를 들어 입력 값으로 1 2 3 4 5 6 7 이 들어왔다고 가정해보자. 그러면 반복문 안에서 count=1 되면서 dfsForRecursive(0,1+" "); 함수 안에 들어가게 된다. 그런 다음에 count가 6이 아니므로 for문으로 들어가게 된다. 이제 dfsForRecursive함수 안에는 iArr[0](v=0) 보다는 큰수의 인덱스로 함수에 들어가게 된다. 이런 식으로 쭉쭉 가다보면 처음으로 StringBuffer에 들어가는 수는 1 2 3 4 5 6 이라는 값이 된다. 그러면 else 밑에 count가 -1되고 함수가 리턴이 된다. 이 함수는 for문 안에서 호출한 dfsForRecursive(5,1 2 3 4 5 +iArr[5]+" ") 이다. 이 함수가 리턴이 된다면 for문의 다음 인덱스 i=6 값으로 함수의 매개변수로 들어간다. dfsForRecursive(6,1 2 3 4 5 +iArr[6]+" ") 이값도 count가 6이 됬음으로 StringBuffer에 append 시켜주고 함수가 끝나게 된다. 그렇다면 더 이상 돌 for의 인덱스가 없으므로 이전의 함수 dfsForRecursive(4,1 2 3 4 +iArr[4]+" ") 함수가 끝나게 되고 다음 dfsForRecursive(5, 1 2 3 4 +iArr[5]+" ")를 호출하게 되는 것이다. 이런 식으로 main 함수 안의 for문이 끝날때까지 반복되게 된다. 그런데 여기서 주의 해야할 점은 dfsForRecursive 함수 안의 for문의 시작인덱스가 v+1이라는 것이다. 왜 자신보다 큰 값을 들어오게 하는 것일까? 이것의 예를 들자면 예를 들어서 값이

1 2 3 4 5 6 , 1 2 3 4 5 7 이라는 결과로 함수가 끝났다고 생각하자 그 다음은 1 2 3 4 6 ? 로 시작을 하게 될 것이다. 여기서 v+1이라는 값이 발휘 한다. 만약 1 2 3 4 6 5 라는 값이 들어오게 되면? 이 문제는 중복을 허락하지 않음으로 바로 위의 1 2 3 4 5 6 이라는 값과 중복이 되버린다. 그래서 v+1을 함으로써 이전에 나왔던 결과값과 중복이 되지 않게 하는 것이다.

입력:

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

출력:

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

재귀를 이용한 하노이탑(백준1914번문제)

재귀를 이용한 하노이탑 문제풀이

여기서 문제는 N값이 20 이하 일때만 원반을 옮기는 과정을 출력하지만 20보다 클 경우에는 원반의 옮긴 수만 출력하면 된다. 여기서 옮긴 횟수를 함수 안에서 재귀호출 할때마다 카운트를 1씩 증가시키는 것으로 코드를 짜게되면 아마 시간 초과가 발생할 것이다.  왜냐면 조건에서의 가장 큰수 100을 입력하면 1267650600228229401496703205375라는 원반을 옮긴 횟수가 나오는데 보통 1억번에 1초정도 걸리는데 이것은 어마어마한 시간이 걸릴 것이므로 횟수는 카운트를 1씩 증가시키는 것이 아니라 점화식을 이용하여 횟수를 구한다.

즉, 원반을 옮기는 횟수는 2^N-1번이다.  N값이 100이라 가정했을 때는, 이 값은 long 데이터 타입도 수용하지 못할 값이므로 자바의 BigInteger 클래스를 이용해 횟수를 저장한다. 내부적으로 String을 가지므로 무한히 큰 값도 수용이 가능하다.

원반을 옮기는 과정의 함수를 설명하자면 예를들어 3개의 원반을 1번탑에서 3번탑으로 옮긴다면 hanoi(3,'1','2','3') 함수를 호출하게 된다. 그러면 함수 내부에서 재귀호출을 통해서 문제를 쪼개는 과정에 들어간다. 3개의 원반을 1번탑에서 3번탑으로 옮기는 것이라면 우선 더 작은 문제로 1번,2번 원반을 2번탑으로 옮긴후에 그다음 3번원반을 3번탑에 옮기고 그리고 1번,2번의 원반을 다시 2번탑에서 3번탑으로 옮기는 것 이렇게 문제를 작은 단위로 쪼개는 것이다. 이것이 총 3번의 과정으로 1번 n-1개의 원반을 보조탑(2번탑으로 옮기는과정)으로 옮기는 과정은 hanoi(2,from,to,aux) 함수에서 해결하고 그다음 3번원반을 1번탑에서 3번탑으로 옮기는 과정은 system.out.println(from+" "+to); 라는 출력문으로 그리고 마지막으로 보조탑에 있던 1번,2번 원반을 3번탑으로 옮기는 과정은 hanoi(2,aux,from,to) 함수에서 해결하게 된다. 그리고 각 함수 내에서 문제를 더 작은 단위로 쪼개고 쪼갠다. 예를 들어 1,2번 원반을 보조탑으로 옮기는 hanoi(2,from,to,aux) 함수에서 다시 문제를 1번원반을 보조탑인 3번탑으로 옮기는 과정(hanoi(1,1,2,3)과 2번원반을 2번탑으로 옮기는 과정(system.out.println(from+" "+to) 그리고 마지막으로 보조탑에 있던 1번원반을 목적탑인 2번탑으로 옮기는과정(hanoi(1,3,1,2))으로 마무리 되는 것이다. 

즉,

 hanoi(N-1,from,to,aux);

System.out.println(from+" "+to);

hanoi(N-1,aux,from,to);

이 과정이 n의 수가 1이 될때까지 계속 각 n값에 대하여 반복하게 되는 것이다.

이 문제같은 경우는 최소신장트리를 구하는 알고리즘이다. 최소신장트리를 구하는 알고리즘은 크게 프림알고리즘과 크루스칼알고리즘 두가지가 있다. 여기서 조금더 구현하기가 수월한 프림알고리즘을 이용하여 최소신장트리를 구현할것이다.

1. 최소신장 트리란?

최소 신장트리란 주어진 그래프에서 모든 정점을 연결하며 그 비용이 최소인 간선만 연결된 트리를 말한다.

2.프림 알고리즘(그림으로 설명하는 것이 편할 것같아 그림으로 ㅅ

다익스트라 알고리즘과 비슷한 로직을 가집니다. 다만 큐에서 최소값을 빼주며 방문한 정점들을 체크를 해주어서 이미 체크된 정점 같은 경우는 결과값에 포함시키지않는다. 

이전에 게시했던 최단 거리문제가 코드가 동일하다. 단지 출력하는 부분의 코드만 살짝 수정해주면된다. 즉, 최소비용문제 또한 다익스트라 알고리즘으로 풀수 있다.

백준-1916번 최소비용 구하기

출발도시에서 도착도시까지의 최소비용을 구하는 것이므로 출력부분을 도착도시의 거리를 출력해주면된다. 왜냐하면 다익스트라 알고리즘은 시작정점으로부터 모든 정점까지의 최소비용들이 모두 distance배열에 들어가기때문에 단순히 앞의 최단경로 문제 코드에서 출력부분만 수정해주면 된다. 다익스트라 알고리즘 구동방식은 최단거리문제 설명에 그림으로 설명되어있다.

백준-1753번 최단거리

시작정점으로부터 모든 정점까지의 최단거리를 구하는 문제이다. 이 문제는 BFS와 비슷한 다익스트라 알고리즘으로 풀 수 있는 문제이다. 다익스트라 알고리즘은 방향이있는 가중치 그래프에서 어떤 정점에서 다른 정점까지의 최단 거리를 구할 수 있는 알고리즘이다.(음수간선을 포함하는 그래프는 다익스트라 알고리즘으로 풀 수 없다.)

위의 그림과 같은 과정으로 다익스트라 알고리즘이 구동됩니다. ( 코드에서는 방문여부에 관한 check배열은 선언하지 않았음 굳이 없어도 돌아감)

BFS와 비슷하게 큐를 이용하지만 그냥 큐가 아니라 우선순위 큐를 이용하여 구현한다. 

1. 위상정렬

위상정렬의 조건

위상정렬이 가능하려면 DAG 그래프여야 한다. DAG란 Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프를 의미한다.

진입차수를 이용한 위상정렬

1.모든 정점의 선행 필요조건 관계를 따라 그래프를 그린다.

(방향 그래프 완성)

2. 각 정점에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)

3. indegree가 0인 일을 모두 찾아 큐에 넣는다

4. 큐에서 정점 하나를 꺼낸다.

(위상정렬의 결과 출력을 위해 이때 꺼내진 정점을 출력하면 된다.)

5. 방금 꺼낸 정점에 연결된 모든 정점들의 indegree를 1씩 감소시킨다.

6. indegree가 감소된 정점들 중 indegree가 0인 정점이 있으면 큐에 넣어준다.

7. 큐가 빌 때까지 4~6을 반복한다.

2.위의 위상정렬을 이용한 백준 2252번 줄세우기 문제)

그래프 DFS(깊이우선탐색) 와 BFS(너비우선탐색)

1. 시작전

그래프를 구현하는 방법 중에는 크게 두 가지가 있습니다. 첫번째는 인접행렬을 이용하는 방법이고, 두번째는 인접리스트를 이용하는 방법입니다. 이 두가지 방법중 인접행렬을 이용한 DFS 와 BFS를 구현해보겠습니다.

2.DFS(깊이우선탐색)

설명:  1번 정점부터 시작하므로 스택에 1번정점을 넣어준다. 그리고 스택에서 peek을 하여 1번정점을 꺼내어 1번정점에 대한 인접행렬의 행을 탐색하여 첫번째로 나오는 visited가 false인 연결정점(2번정점)을 visited=true로 바꿔주고 스택에 넣어준다. 그리고 다시 스택에서 peek을 하여 이전에 넣었던 2번정점을 읽어와 2번정점에 대한 인접행렬 행을 읽어 첫번째로 나오는 visited가 false인 연결정점(4번정점)을 visited=true로 바꿔 주고 스택에 넣어준다. 이런 과정을 진행하다가 막다른 지점이 나오면(4번정점) 그에 대한 인접행렬의 행에서 visited가 false 인접한 정점이 존재하지 않으므로 스택에서 pop해주어 백트래킹을 진행한다. 그러다 1번정점에서 다시 visited가 false 인접정점이 존재하므로 위의 과정을 반복하게 된다.

3.BFS(너비우선탐색)

설명: 시작정점 1번을 방문후 큐에 삽입해준다. 그리고 큐에서 poll을 해서 1번정점을 빼주고 1번노드 다음레벨에 해당하는(인접하고있는) 정점들을 모두 방문 후 큐에 삽입해준다.(2번정점 3번정점) 그리고 큐에서 poll을 해서 2번정점을 빼주고 2번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(4번정점) 그다음 큐에서 poll을 해 3번 정점을 빼주고 3번 정점 다음레벨에 해당하는 정점들을 모두 큐에 삽입해준다.(5,6,7번정점).. 이과정을 반복해준다.

4. 백준 1260번 DFS와 BFS