[코드업 기초 100제 - 99번 성실한 개미]

 

🔒 문제

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

 

이정도 난이도 문제는 별도의 함수 정의가 필요하지 않아서

설계 문서와 Flow chart를 생략한다.

 

🔑 Key Idea

이동의 우선순위가 →↓ 이다. 따라서 

2차원 배열을 늘여놓았을 때 

 

 

목적지 2까지 선 우방향검사 후 하방향 검사하는 식을 세우는 것이 Key 였다.

 

 

⚠️ 주의! 배열을 이용한 문제에서 항상 주의해야 할 것은 인덱스 범위이다.

반복문 조건식에 index 범위를 제한해 주는것이 필수! (∵ 범위내 목적지를 찾지못하면 끝을 넘어가게 됨)

인덱스 번호가 0부터 시작하는 배열 특성상 core dump (Segmentation Fault)의 발생 가능성이 높기 때문이다.

---

👨🏻‍💻 구현 in C++

#include <iostream>
using namespace std;
 
int main(void)
{
 
  
    int arr[11][11] = {0};
    int i, j;
    for(int i = 1; i <= 10; i++)
    {
        for(int j = 1; j<= 10; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    i = 2, j = 2; //출발점 setting  
    
    while(arr[i][j] != 2 && i <= 10 && j <= 10) // out of index 방지 
    {
        if(arr[i][j+1] != 1) // 오른쪽 검사  
        arr[i][j++] = 9;
        else if(arr[i+1][j] != 1) // 아래쪽 검사  
        arr[i++][j] = 9;
        else
        break;
    }
    arr[i][j] = 9; // 마지막 도달한 지점은 9로 이미 도달한 상태. // 도착점 setting 
    
        for(int i = 1; i <= 10; i++)
    {
        for(int j = 1; j<= 10; j++)
        {
            cout << arr[i][j] << ' ';
        }
        cout << '\n';
    }
    
    return 0;
}

 

주석을 달아놓았으니 참고 '-'

 

👨🏻‍💻 소스코드 (재귀 버전)

#include <iostream>
using namespace std;
 
int arr[11][11]; //2차원 배열 Parameter로 넘기기 성가셔서 전역변수 선언
 
void move(int rowIndex,int colIndex)// 목적지 도달까지 현위치 9 업데이트하며 검사  
{
    if(arr[rowIndex][colIndex] == 2)
    {
        arr[rowIndex][colIndex] = 9;
        return;
    }
    arr[rowIndex][colIndex] = 9; // 현위치가 2만 아니면 9로 업데이트. 
    if(arr[rowIndex][colIndex+1] != 1)
    {
        move(rowIndex, ++colIndex);      
    }
    else if(arr[rowIndex+1][colIndex] != 1)
    {
        move(++rowIndex, colIndex);
    }        
}
int main(void)
{
    int i, j;
    for(i = 1; i <= 10; i++)
    {
        for(j = 1; j <= 10; j++)
        {
            cin >> arr[i][j];
        }
    }
    
    move(2, 2); // 시작점 (2,2) 
    
    for(i = 1; i <= 10; i++, puts(""))
    {
        for(j = 1; j <= 10; j++)
        {
            cout << arr[i][j] << ' ';
        }
    }
    return 0;
}

 

 

재귀버전은 함수 호출이 더 많다.

정답인지 아닌지 선검사 하는거부터가 (정답인 경우는 딱 1case, 정답 2에 도달한 시점밖에 없으므로)

시간복잡도 또한 이전 풀이 보다는 약간 높은 알고리즘이 된다.