색칠 문제 - 백트래킹(Backtracking) 상태 공간 트리와 알고리즘

색칠 문제 - 백트래킹(Backtracking) 상태 공간 트리와 알고리즘

---

서론

상태 공간 트리(State Space Tree)는 문제 해결 과정의 중간 상태를 각각 한 노드로 나타낸 트리입니다.

 

백트래킹(Backtracking)은 상태 공간 트리에서 새로운 탐색이 무의미하다고 판단되면, 다른 새로운 탐색이 가능한 선택 포인트(choice point)로 backtrack하여 새로운 탐색을 시도합니다.

더 이상의 선택 포인트가 존재하지 않으면, 탐색은 실패로 끝납니다.

되추적은 갈림길에 표시를 해두고 막다른 골목에 다다르면 갈림길까지 되돌아가서 다른 골목으로 가보는 방법입니다.

깊이 우선 탐색과 관련 있습니다.

 

색칠 문제(Coloring Problem)는 주어진 그래프에서 인접한 정점은 같은 색을 칠할 수 없는 조건 하에서 k개의 색상을 사용하여 전체 그래프를 칠할 수 있는지 알아보는 문제입니다.

---

본론

색칠 문제 백트래킹 알고리즘 의사코드

 

valid(i, c) 의사코드

---

문제 1. 색칠 문제를 푸는 백트래킹 알고리즘을 사용하여 빨간색,녹색,흰색의 3가지 종류의 색을 가지고 아래 그래프를 색칠하는 것이 가능한지를 판단하기 위한 실행절차를 제시하시오.

 

kColoring(1, 1)

kColoring(1, 1)

1) valid(1, 1)은 True를 반환

2) color[1] 에 빨간색(1) 저장

3) kColoring(1, 1)의 while문에서 kColoring(2, 1) 호출

kColoring(1, 1)

 

 

kColoring(2, 1)

kColoring(2, 1)

1) valid(2, 1)은 False를 반환

2) kColoring(1, 1)의 while문으로 돌아감

3) d++;

4) kColoring(2, 2) 호출

kColoring(2, 1)

 

kColoring(2, 2)

kColoring(2, 2)

1) valid(2, 2)은 True를 반환

2) color[2] 에 녹색(2) 저장

3) kColoring(2, 2)의 while문에서 kColoring(3, 1) 호출

kColoring(2, 2)

 

kColoring(3, 1)

kColoring(3, 1)

1) valid(3, 1)은 True를 반환

2) color[3] 에 빨간색(1) 저장

3) kColoring(3, 1)의 while문에서 kColoring(4, 1) 호출

 

kColoring(3, 1)

 

kColoring(4, 1)

kColoring(4, 1)

1) valid(4, 1)은 False를 반환

2) kColoring(3, 1)의 while문으로 돌아감

3) d++;

4) kColoring(4, 2) 호출

kColoring(4, 1)

 

kColoring(4, 2)

kColoring(4, 2)

1) valid(4, 2)은 True를 반환

2) color[4] 에 녹색(2) 저장

3) kColoring(4, 2)의 while문에서 kColoring(5, 1) 호출

 

kColoring(4, 2)

 

kColoring(5, 1)

kColoring(5, 1)

1) valid(5, 1)은 True를 반환

2) color[5] 에 빨간색(1) 저장

3) kColoring(5, 1)의 while문에서 kColoring(6, 1) 호출

kColoring(5, 1)

 

kColoring(6, 1)

kColoring(6, 1)

1) valid(6, 1)은 False를 반환

2) kColoring(5, 1)의 while문으로 돌아감

3) d++;

4) kColoring(6, 2) 호출

kColoring(6, 1)

 

kColoring(6, 2)

kColoring(6, 2)

1) valid(6, 2)은 True를 반환

2) color[6] 에 녹색(2) 저장

3) i=n=6 이므로, True 반환하고 함수 종료

kColoring(6, 2)

---

결론

kColoring(6, 2)

색칠 문제를 위한 백트래킹 알고리즘을 통해 문제로 주어진 그래프에 대응되는 상태 공간 트리는 위와 같습니다.

kColoring(6, 2)

그리고 위 상태 공간 트리를 통해 색칠한 그래프는 위와 같습니다.

총 두가지 색(빨간색, 녹색)을 가지고 그래프를 색칠할 수 있었습니다.

 

문제에서 물어보는 "빨간색, 녹색, 흰색의 3가지 종류의 색을 가지고 아래 그래프를 색칠하는 것이 가능한지"에 대하여,

총 세가지 색을 무조건 모두 사용하여야 하는지, 아니면 세가지 색에서 두가지 색만 사용해도 되는지 말이 모호하고 헷갈렸습니다.

그러나 통상 위 문구가 의미하는 바는 k == 3 가 아니라 k <= 3 을 의미하므로, k = 2 일 경우도 문제의 조건에 해당한다고 생각합니다.

따라서, 정답은 3가지 종류의 색으로 그래프를 색칠하는 것이 가능하다고 생각합니다.

---

이번 시간 색칠 문제를 통해, 상태 공간 트리란 무엇이고 상태 공간 트리를 통해 탐색하는 방법에 대해 알게 되었습니다.

상태 공간 트리 중에는 백트래킹 기법이라는게 있다는 사실을 알게되고, 백트래킹 기법의 원리에 대해 이해하게 되었습니다.

백트래킹 기법을 응용하여 색칠 문제를 풀어보면서, 백트래킹 알고리즘의 과정을 보다 자세하게 이해할 수 있었습니다.