지뢰찾기

지뢰찾기

1966번 지뢰찾기

문제 설명

다들 windows에서 지원하는 지뢰 찾기 게임을 한번쯤은 해 보았을 것이다. 특히 동호는 지뢰찾기의 매니아로 알려져 있다. 지뢰 찾기 map은 N*N의 정사각형 모양으로 각 칸에는 숫자가 들어가 있거나 지뢰가 들어가 있다. 빈 칸에는 숫자 0이 들어있다고 생각하자.

map의 어떤 칸에 적혀 있는 숫자는, 그 칸과 인접해 있는 여덟 개의 칸 중에서 지뢰가 들어 있는 칸이 몇 개인지를 나타내 준다. 물론 인접한 칸이 map 내부에 있는 경우에 대해서만 생각하면 된다. 예제를 보면 더 잘 이해할 수 있을 것이다.

이번 문제는 조금 업그레이드 된 지뢰 찾기로, 한 칸에 한 개의 지뢰가 있는 것이 아니고, 한 칸에 여러 개(1 이상 9 이하)의 지뢰가 묻혀 있는 게임이다. 따라서 map의 어떤 칸에 적혀 있는 숫자는, 그 칸과 인접해 있는 여덟 개의 칸들에 들어 있는 지뢰의 총 개수가 된다.

이미 windows 지뢰찾기 같은 것을 마스터한 영식이는, map에서 지뢰에 대한 정보만이 주어졌을 때, 영식이는 map을 완성하고 싶다고 한다. N과 지뢰의 위치가 주어졌을 때, 영식이를 도와서 지뢰 찾기 map을 완성하는 프로그램을 작성하시오.

입력		출력
N	5	[ [ '*', 4, 3, 3, 0 ], [ 1, 4, '*', 3, 0 ], [ 4, 7, 7, 3, 0 ], [ 4, '*', 'M', 9, 9 ], [ 4, 4, 'M', '*', 9 ] ]
arr	[ ['1', '.', '.', '.', '.'], ['.', '.', '3', '.', '.'], ['.', '.', '.', '.', '.'], ['.', '4', '.', '.', '.'], ['.', '.', '.', '.', '9'] ]

문제풀이

이차원 배열이나 맵을 사용하지 않고 풀었다. 그래서 다소 복잡하게 풀었는것 같다.

function solution(N, arr){
	// reduce의 누산기를 활용 2차원 배열을 1차원 배열로 바꾼다
    let arrOne = arr.reduce(function(acc, cur){
       return [...acc,...cur]
    })
    let returnArr = new Array((N*N)).fill(0) // 리턴하기 위한 배열
    
    // arrOne은 지뢰의 위치와 지뢰의 피해량을 가지고 있다.
    arrOne.map((v,X)=>{
        // 값이 .이 아닌 경우 = 즉, 지뢰의 위치(인덱스)와 피해량(값)을 가지고있는 경우
        if(v !== '.'){
            // 피해범위 구하기
            let ranges = [X+N, X-N, X-1, X+1, (X+N)-1, (X+N)+1, (X-N)-1, (X-N)+1]
            
            // 좌측 끝인 경우의 피해범위
            if(X%N === 0 ){ 
                ranges = [X-N, X+N, (X-N)+1, (X+N)+1, X+1]
            }
            
            // 우측 끝인 경우 피해범위
            if((X%N)+1 === N){
                ranges = [X-N, X+N, (X-N)-1, (X+N)-1, X-1]
            }

            // 피해범위 위치값을 가지고 있는 (ranges)에서 유효한 위치값만 구하기
            let effectiveRanges = ranges.filter((range)=>{
                return (range > 0) && (range < N*N)
            })

            // 유효한 위치값을 순회 하면서 피해유효범위에 피해량 기록하기
            effectiveRanges.forEach((range)=>{
                returnArr[range] = returnArr[range]+Number(v)
            })
        }
    })
    arrOne.map((v,x)=>{
        if(v !== '.'){
            // 반환 배열의 지뢰위치에 지뢰 표시
            returnArr[x] = '*' 
        }else{
            // 반환 배열의 값이 10을 넘으면 M표시
            if(returnArr[x]>10){
                returnArr[x] ='M'
            }
        }
    })
    
    // 2차원 배열로 답 만들어주기
    let answer=[];
    for(let i=0; i<N; i++){
        answer.push(returnArr.slice(i*N,(i*N)+N))
    }  
	return answer;
}

 

2차원 배열을 1차원 배열로 반환한 뒤  지뢰의 위치에서 8방향을 구하여 해당 방향에 지뢰의 영향도를 합하여 넣어주면 된다고 생각했다.

1차원 배열에서 8방향을 구하는 방식을 고민을 많이 했다. 

    arrOne.map((v,X)=>{
        // 값이 .이 아닌 경우 = 즉, 지뢰의 위치(인덱스)와 피해량(값)을 가지고있는 경우
        if(v !== '.'){
            // 피해범위 구하기
            let ranges = [X+N, X-N, X-1, X+1, (X+N)-1, (X+N)+1, (X-N)-1, (X-N)+1]
            
            // 좌측 끝인 경우의 피해범위
            if(X%N === 0 ){ 
                ranges = [X-N, X+N, (X-N)+1, (X+N)+1, X+1]
            }
            
            // 우측 끝인 경우 피해범위
            if((X%N)+1 === N){
                ranges = [X-N, X+N, (X-N)-1, (X+N)-1, X-1]
            }

            // 피해범위 위치값을 가지고 있는 (ranges)에서 유효한 위치값만 구하기
            let effectiveRanges = ranges.filter((range)=>{
                return (range > 0) && (range < N*N)
            })

            // 유효한 위치값을 순회 하면서 피해유효범위에 피해량 기록하기
            effectiveRanges.forEach((range)=>{
                returnArr[range] = returnArr[range]+Number(v)
            })
        }
    })

 

처음에는 아래처럼 N*N 의 이차원 배열이 주어질때 이걸 N개씩 끊어서 일차원으로 만들면 된다고 생각했다.

그런데 합이 이상하게 진행되어서 살펴보니 가장자리의 경우 유효범위를 다르게 해주어야 했다.

일차원으로 변경했을때 가장자리의 위치에서 -1을 하게되면 다른 범위를 가르키기 때문이다. 

2차원 배열에서 (A+N)-1은 정상적으로 A 지뢰의 유효범위이지만

 

1차원 배열에서는 전혀 다른 값을 가르킨다.

 

2차원 배열을 2차원 배열로 풀거나 혹은 맵형태를 사용해서 구현했으면 쉬웠을텐데 생각이 나지 않아서 어렵게 구현한 것 같다.