[SW Expert] #1211. [S/W 문제해결 기본] 2일차 - Ladder2

https://swexpertacademy.com/main/main.do

SW Expert Academy

1. 해결방법

많이 볼 수 있는 DFS 문제로 좌, 우, 아래 순으로 한 번만 체크하는 방식으로 해결하면 금방 풀 수 있을 거라 생각했다.

---

2. 에러

먼저 100X100 배열을 가로로 입력받아야 하는데 다음과 같은 코드로 세로를 먼저 받게 입력받았다. 이사실을 오랫동안 알아차리지 못해 문제에 오류가 생겼다. 주의하자 array[i][j]가 아닌 [j][i] 여야 한다

        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100; j++){
                cin >> array[i][j];
            }
        }

---

3. 코드

#include<iostream>

using namespace std;
int array[100][100] = {0};
int chk_array[100][100] = {0};
int result = 0;
int max_value = 9999;
int nx[3] = {-1, 1, 0};
int ny[3] = {0, 0, 1};

void dfs(int x, int y, int start, int count){
    if (y == 99){
        if(count <= max_value){
            max_value = count;
          	result = start;
        }
    }
    else{
        for(int i = 0; i < 3; i ++){
     		int dx = x + nx[i];
        	int dy = y + ny[i];

        	if(dx < 0 || dx >= 100 || dy < 0 || dy >= 100 || chk_array[dx][dy] == 1 || array[dx][dy] == 0 || (y == 0 && i == 0) || (y == 0 && i ==1)) continue;
			else{
                chk_array[dx][dy] = 1;
             	dfs(dx, dy, start, count+1);
                chk_array[dx][dy] = 0;
                break;
            }
    	}
        
    }    
}

int main(int argc, char** argv)
{
   int test_case;
   int T;   
   for(test_case = 1; test_case <= 10; ++test_case)
   {
      cin>>T;
        for(int i = 0; i < 100; i++){
            for(int j = 0; j < 100; j++){
                cin >> array[j][i];
            }
        }
        result = 0; max_value = 9999;
        for(int k = 0; k < 100; k++){
            chk_array[k][0] = 1;
            dfs(k, 0, k, 1);
            chk_array[k][0] = 0;
        }
        cout << "#" << test_case << " " << result << endl;

   }
   return 0;//정상종료시 반드시 0을 리턴해야합니다.
}