코딩테스트-알고리즘-등굣길

프로그래머스 코딩테스트 등굣길을 풀어봤다.

문제는 아래와 같다.

 

https://programmers.co.kr/learn/courses/30/lessons/42898

코딩테스트 연습 - 등굣길

 

배열을 순회하면서 위에꺼와 왼쪽꺼를 더해주면 쉽게 풀 수 있는 문제이다.

아래는 제가 짠 코드입니다.

public class 등굣길 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] puddles ={{2, 2}};
		System.out.println("answer : "+solution(4,3,puddles));
	}
	
	//n은 세로길이(y) m은 가로길이(x)
	public static int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        
        //길의 개수를 저장할 변수
        int[][] retArr=new int[n][m];
        //1으로 배열 초기화 단 장애물 있는 부분만 0으로 초기화
        initArr(retArr,puddles);

        
        for(int y=0;y<n;++y) {
        	for(int x=0;x<m;++x) {
        		//맨처음 지점은 패스 || 장애물지점도 패스
        		if( (y==0 && x==0) || retArr[y][x]==0) {
        			continue;
        		}else if(y==0) {
        		//맨 윗줄의 경우 내자리뒤에있는것만 가지고오면 된다.
        		//더하는 것이 아님!
        			retArr[y][x]=retArr[y][x-1];
        		}else if(x==0) {
        		//맨 왼쪽줄의 경우도 마찬가지.위에꺼를 그냥 가져오면 된다.
        			retArr[y][x]=retArr[y-1][x];
        		}else {
        		//중간줄의 경우 내자리 = 위에꺼 + 왼쪽꺼
        			//찾은게 int값을 넘을수도 있어서 1000000007로 나눈나머지를 넣어줘야 효율성테스트에서 통과됨.
        			retArr[y][x]=(retArr[y-1][x]+retArr[y][x-1])%1000000007;
        		}
        	}
        	printArr(retArr);
        	System.out.println();
        }
        answer = retArr[n-1][m-1];
        return answer;
    }

	public static void initArr(int[][] arr,int[][] puddles) {
		for(int i=0;i<arr.length;i++) {
			for(int j=0;j<arr[i].length;j++) {
				arr[i][j]=1;
			}
		}
		//물에잠긴지역이 있을 경우 해당 부분만 0으로 초기화
		if(puddles.length>0)
			for(int i=0;i<puddles.length;i++) {
				//장애물이 있는 지점
				int x = puddles[i][0]-1;
				int y = puddles[i][1]-1;
				//x y 바뀌지 않도록 주의.
				arr[y][x]=0;
			}
	}
	
	public static void printArr(int[][] arr) {
		for(int i=0;i<arr.length;i++) {
			for(int j=0;j<arr[i].length;j++) {
				System.out.print(arr[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	
}

 

가로축,세로축 햇갈리지 않는게 첫번째로 중요하고

두번째는 조건에따라 위에꺼와 왼쪽꺼 길찾은 것을 더해 저장하는 것입니다.

그리고 효율성 테스트를 위해 배열에 값을 저장할 때 1000000007로 나눈 나머지를 저장해야합니다.

(이 부분은 제가 찾아본 결과 길을 찾은 개수가 int값을 넘을 수 있어서 1000000007나눈 나머지를 저장해야 한다고 합니다. 실제 이 부분이 있어야 효율성테스트에서 통과가 되고, 실행시간도 약 절반가량 줄어들었습니다.)

 

-끝-