인프런 커뮤니티 질문&답변

안녕하세요 완섭님 ㅎㅎ

지금 이 코드 실행해봤는데요.

예제 7번 입력했을 때 2가 아니라 -1이 뜨는데 확인해보시겠어요?

또한 주석 달았으니 확인 부탁드립니다.

#include <bits/stdc++.h>
using namespace std;

int n, m, h;
int sadari[40][15]; 
bool visited[40][15];
int ans = 987654321;

bool check() {
    // good
	for (int j = 1; j <= n; j++) {
		int num = j;
		for (int i = 1; i <= h; i++) {
			if (sadari[i][num]) num++;
			else if (sadari[i][num - 1]) num--;
		}
		if (num != j) return false;
	}
	return true;
}

void go(int row, int col, int num, int level) {
    // good 
	if (num > 3 || num >= ans) { return; }
	
	if (check()) {
		ans = min(ans, num);
		return;
	}
	// 이거요. 왜 i는 1부터 시작하시나요? 
    // 이렇게 하면 재귀함수를 돌려도 계속해서 go(1, 1) 부터 확인해나가며 비효율적
    // (물론  visited로 거르겠지만) 이지 않을까요?
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j < n; j++) {
			if (sadari[i][j]||visited[i][j]) continue;

			visited[i][j] = true;
			go(i, j, num, level+1);
			if (!(sadari[i][j - 1] || sadari[i][j + 1])) {
				sadari[i][j] = 1;
				go(i, j, num + 1, level+1);
				sadari[i][j] = 0;
			}
			
			
		}
	}
}

int main(void)
{
	cin >> n >> m >> h;
	
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		sadari[a][b] = 1;
	}
 
	visited[1][1] = true;
	go(1, 1, 0, 1);
	if (!sadari[1][1] && !sadari[1][2]) {
		sadari[1][1] = 1;
		go(1, 1, 1, 1);
		sadari[1][1] = 0;
	}

	if (ans > 3) cout << -1;
	else cout << ans;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

감사합니다.

강사 큰돌 올림.