[코드업] 기초 100제 자바 - 복습5

코드업 100제 문제를 자바로 풀면서 헷갈렸던 부분에 대해서 정리한다.

 

[기초-2차원배열] 성실한 개미

 

문제  설명 * 

 

영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다.

왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데,
그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다.

개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다.
(오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.)

이에 호기심이 생긴 영일이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다.

미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지
오른쪽 또는 아래쪽으로만 움직였다.

미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고,
먹이가 2로 주어질 때, 성실한 개미의 이동 경로를 예상해보자.

단, 맨 아래의 가장 오른쪽에 도착한 경우, 더 이상 움직일 수 없는 경우, 먹이를 찾은 경우에는
더이상 이동하지 않고 그 곳에 머무른다고 가정한다.


미로 상자의 테두리는 모두 벽으로 되어 있으며,
개미집은 반드시 (2, 2)에 존재하기 때문에 개미는 (2, 2)에서 출발한다.

 

 

코드 *

 

int[][] map = new int[100][100];

        for(int i = 1; i <= 10; i++) {
            for(int j =1; j <= 10; j++) {
                map[i][j] = 0;
            }
        }

        for(int i = 1; i <= 10;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j <= 10; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int cnt = 2;
        boolean s = false;

        for(int i = 2; i <= 10;i++) {
            // cnt 현재 벽에 만났을때 j값을 저장하기위함.
            for(int j = cnt; j <= 10; j++) {

                if(map[i][j] == 2) {
                    map[i][j] = 9;
                    s = true;
                    break;
                }

                if( map[i][j] == 0 ) {
                    map[i][j] = 9;
                } else if( map[i][j] == 1 ) {
                    cnt = j - 1;
                    break;
                }
            }
            if(s) {
                break;
            }
        }

 

PS) 이문제는 2차원 배열과 반복문 조건문을 활용하는 문제이고 

       처음에는 많이 헷갈렸고 개미가 이동할 경로에 대해 9를 출력후 멈추면된다.

       문제의 가장 핵심은

        "개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다"

       이부분이며 이떄의 조건식을 잘세우고 return 처리하면된다.

       벽을 만나면 해당하는 y축을 -1 해서 기존 x축으로 돌아가서 올려주면 된다. 

       이해하기 쉽게 밑에 간단하게 그림을 그렸다.

        

 

        길이 = 5

 

        1 1 1 1 1
        1 0 0 1 0
        1 0 0 1 0
        1 0 0 0 0
        1 0 0 2 0
        

        길이 5인값을 2차원 배열로 나타냈을때 그림이다 

        9는 현재 [2,3]을 9라고 표현한거고 

        1는 현재 [2,4]을 1라고 표현한거다.

        정리하자면 현재 y축의 4라는 값을 j - 1를 통해서 

        [x,3] 배열로 이동한거다. 

        1을 만날 경우 이 부분을 계속 반복한다.

        [1,1][1,2][1,3][1,4][1,5]
        [2,1][2,2][2,3=9][2,4=1][2,5]
        [3,1][3,2][3,3][3,4=1][3,5]
        [4,1][4,2][4,3][4,4][4,5]
        [5,1][5,2][5,3][5,4][5,5]

       

       

       행렬(2차원배열)이 이해가 안된다면 아래 그림을 확인하자.