그리디 알고리즘?

1. 문제

기다란 다리가 있습니다. 다리가 낡아 여기저기 구멍이 나서 지나가는 사람들이 종종 물에 빠지곤 합니다.

다리의 구멍을 메우기 위해서 한 칸을 이동하는 데에는 1분이 걸립니다.

다만, 배를 타고 다리의 끝으로 이동할 경우 1분이 걸립니다.

구멍이 난 곳을 1, 멀쩡한 곳을 0으로 표시한 배열 bridge가 주어졌을 때,

다리를 보수하기 위해 이동하는데 걸리는 총시간을 구하십시오.

예) 아래와 같은 다리의 경우

현위치

0

0

0

0

0

1

1

배를 타고 이동하는데 1분 + 옆으로 한 칸 이동하는데 1분 총 2분이 소요됩니다.

 

2. 풀이과정

			firstX			lastX
	0	0	1	0	0	1	0	0	0

위와 같이 처음 구멍이 난 곳을 firstX라 하고, 마지막으로 구멍이 난 곳을 lastX라 할 때,

배를 타지 않고 다리를 건너는 경우 최소한 lastX까지는 가야 하고, (6)

배를 타고 반대편에서 오는 경우 최소한 firstX까지는 가야합니다. (7)

답은 둘 중 더 작은 값인 6입니다.

다만, 예외적으로 다리를 건너다가 다시 돌아와 배를 타는 것이 더 빠른 경우가 있습니다.

1

1

1

0

0

0

0

0

1

1

이렇게 앞 뒤에만 구멍이 몰려있는 경우입니다.

이런 케이스를 해결하기 위해서 longestA 로 가운데 있는 가장 긴 멀쩡한 구간의 길이를 측정합니다.

00000을 l이라 하고, l을 기준으로 좌측의 111을 a 우측의 11을 b라 할 때

그대로 직진하는 경우는 a+(l - 1)+b라는 시간이 소요되며 (예제의 경우 3 + 4 + 2 = 9)

돌아가 배를 타는 경우는 2(a - 1) + b 시간이 소요됩니다. (예제의 경우 4 + 2 = 6)

2(a - 1) + b < a + l - 1 + b 를 계산하면

a - 1 < l 인 경우는 돌아가서 배를 타는 것이 더 빠르다는 결론이 나옵니다.

다만, 위와 같이 가장 긴 구간을 중심으로 좌우에 구멍이 나있는 경우에만 적용되도록 세밀하게 조건을 지정할 필요가 있습니다. 

3. 구현

public int solution(int[] bridge) {
             
       int firstX = 0, lastX = 0, longestA=0, firstA=0, lastA=0, temp=0, j=0;
       int total=0;
       
       for(int i = 1; i < bridge.length; i++) {
    	   
    	   if(bridge[i]!=0&&firstX==0) {
    		   firstX = i;
    	   }
    	   else if(i > j){
    		   j = i;
    		   while(j<bridge.length&&bridge[j]==0) {
    			   j++;
    		   }
    		   if(j-i > longestA) {
    			   longestA = j-i;
    			   firstA = i;
    			   lastA = j-1;
    		   }
    	   }
       }
       
       for(int i = bridge.length-1; i > 0; i--) {
    	   if(bridge[i]!=0&&lastX==0) {
    		   lastX = i;
    		   break;
    	   }
       }
       
       if(firstX!=0&&lastX!=0&&longestA>1&&firstA -1 < longestA) total+= (firstA-1)*2 + bridge.length - lastA - 1 ;
       else total+= lastX > bridge.length-firstX ? bridge.length-firstX : lastX; 
       
       return total;
    }

 

4. 반성

위 코드를 작성하는 데에도 적지않은 시간과 시행착오가 있었지만, 완성시켜놓고 보니 이게 과연 그리디 알고리즘이 맞나 하는 의문이 들었습니다.

그리디 (탐욕법) 는 부분 최적해가 전체 최적해가 되도록 하는 기법입니다.

대표적인 예로 최단 경로를 찾을 때, 현 위치에서 건너야 하는 다리를 하나씩 늘려가면서 최소거리인지 여부를 판단하는 다익스트라 알고리즘을 들 수 있습니다.

위 문제를 그리디 알고리즘으로 해결하려면 수학적인 계산을 하기보단

현재의 위치에서 돌아가는 것과 직진하는 것의 비용을 계속 비교하면서 더 빠른 길을 선택하도록 구현했어야 했을 것 같다는 생각이 듭니다.

 

관련 문제 : 프로그래머스 조이스틱 문제 https://programmers.co.kr/learn/challenges