가치 그래프를 활용해서 문제 풀기 - 순한맛

전에 설명했었던 그래프에 가치망을 더해서 문제풀이를 해보겠다.

 

특히 넓이우선 탐색의 문제 풀이에서는 다른 풀이방법들(그리디, 백트래킹)로는 정상적인 답 도출이 어려운 문제들을 그래프로 풀어보겠다.

 

간단한 가치망을 가지고 있는 깊이 우선 탐색문제부터 풀어보도록하자.

 

[문제 출처] jungol.co.kr

태현이는 방학기간 동안 택배 알바를 해서 최고급 노트북을 장만하려고 한다.

오늘 배달해야 하는 장소를 한 번씩만 방문해서 물건을 모두 배달하고 다시 회사로 돌아와야 한다.

배달하는 장소에만 도착할 수 있다면 물건은 모두 배달할 수 있으므로 물건의 개수나 크기등은 고려하지 않아도 된다.

 

그런데 문제는 방문하는 순서를 어떻게 정할지가 고민이다. 

어떤 장소에서 다른 장소로 이동하는 데에는 비용이 발생하는데 만약 방문하는 순서를 잘못 정하게 되면

알바비로 받은 돈을 모두 이동비용으로 사용하고 눈물을 흘릴지도 모른다.

 

태현이가 물건을 모두 배달하고 회사로 돌아오기 위한 최소의 비용을 계산하는 프로그램을 작성해 주자.

첫 줄은 배달해야 하는 장소의 수 N(1≤N≤12)이 주어진다. 이때, 출발지(회사)는 1번이다. 둘째 줄은 N X N 크기의 장소와 장소를 이동하는 비용(0 ≤ 비용＜ 100)이 한 칸씩의 공백으로 구분하여 주어진다. 비용은 양방향이 아니라 단방향으로 가기 위한 비용이다. 예들 들어 첫 번째 행 두 번째 열에 적힌 비용은 1번 장소에서 2번 장소로 이동하기 위한 비용을 의미하며, 2번 장소에서 1번 장소로 이동하기 위한 비용은 두 번째 행 첫 번째 열에 주어진다. 장소 사이에 이동할 수 있는 방법이 없다면 비용을 0으로 표시한다.

 

 

일단 돌아야하는 정점의 갯수가 12개로 적은 편이다.  백트래킹으로 충분히 돌 수 있는 양이다.

 

여러가지 경로를 탐색하고 최대/최소의 가치를 찾아내는 종류의 문제들은 대부분 깊이 우선 탐색으로 풀어낼 수 있다.

 

한 정점을 한번씩만 방문해야하므로 체크 배열과 가치망을 담을 배열이 필요하다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그냥 단순하게 체크용 배열에 방문 여부를 찍으면서 전부 돌아보는 방식이다. 

 

그냥 가치망에 0혹은 그 이상의 수로 갈 수 있는지 없는지 여부를 정해놓고 

 

방문체크 배열을 보면서 모든 루트을 한번 씩 전부 방문해보며 최저값을 구한다.

 

루트 하나의 비용을 선정하기 위해서는 그 루트를 끝까지 타고 들어가야하므로 깊이 우선 탐색이 알맞은 문제라고 할 수 있다.

 

 

 

다음은 기본적인 넓이우선탐색 문제이다. 

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 

토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

 

 

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 

보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 

하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 

대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 

철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.

 

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 

며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 

단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.

입력파일의 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N 은 상자의 세로 칸의 수를 나타낸다. 단, 2≤M,N≤1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N 개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M 개의 정수로 주어진다. 정수 1 은 익은 토마토, 정수 0 은 익지 않은 토마토, 정수 -1 은 토마토가 들어있지 않은 칸을 나타낸다.

다음은 넓이 우선 탐색 문제이다. 

 

우선 배열의 가로 세로 길이가 1000이다. 일반적인 4방향 재귀호출로는 해결이 불가능하다.

 

심지어 토마토가 1개가 아니라 더 많이 있을 수 도 있기 때문에 백트래킹이 아닌 그래프로 풀어야한다.

 

큐에 토마토의 x, y좌표 뿐만 아니라 시간을 나타내는 칼럼을 하나 추가해서 시간을 카운트 한다. 

 

함수를 호출하는 것 자체가 스택을 새로 할당하는 행위이기 때문에 수만번의 함수호출을 하는 재귀호출로는 무조건 오버헤드가 생길 수 밖에 없는 문제였다. 

 

 

 

p.s. 쓴다고 썼는데 막상 쓰고보니 설명이 너무 부족한 것 같다.

보는 사람 있을지 모르겠는데 모르거나 궁금한거 있으면 물어보시면 무조건 대답해드림