알못에서 잘알까지

    2번 문제   

    내가 풀이한 답   

 문제에서는 7 X 7 형태로 정해져 있었지만 이해를 위해 3 X 3을 기준으로 생각을 해보았다. 한 좌표에서 위, 아래, 오른쪽, 왼쪽을 접근하려면 더 큰 인덱스가 필요했다. 그 결과 (N+2) X (N+2) 형태면 가능하다고 보았다. 아래 그림에서 도착점까지 갈 수 있는 방법은 총 두 가지고 그 중 한 가지의 시퀀스는 다음과 같다. →, ↓, ←, ↑ 순서로 탐색한다고 가정했다.

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

int map[9][9], check[9][9], cnt = 0;
int x[4] = {1, 0, -1, 0};
int y[4] = {0, 1, 0, -1};

void dfs(int a, int b){
	int xx, yy, i;
	if(a==7 && b==7) cnt++;
	else {
		for(i=0; i<4; i++){
			xx = x[i] + a;
			yy = y[i] + b;
			
			if(xx < 1 || yy < 1 || xx > 7 || yy > 7) continue;
			if(map[xx][yy] == 0 && check[xx][yy] == 0){
				check[xx][yy] = 1;
				dfs(xx, yy);
				check[xx][yy] = 0;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int i, j;
	
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			cin >> map[i][j];		
		}
	}	
	
	check[1][1] = 1;
	dfs(1, 1);
	
	cout << cnt;
	
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

#include<stdio.h>
int map[10][10], ch[10][10];
int dx[4]={1, 0, -1, 0};
int dy[4]={0, 1, 0, -1};
int cnt=0;

void DFS(int x, int y){	
	int xx, yy, i;
	if(x==7 && y==7){
		cnt++;
	}
	else{
		for(i=0; i<4; i++){
			xx=x+dx[i];
			yy=y+dy[i];
			if(xx<1 || xx>7 || yy<1 || yy>7)
				continue;
			if(map[xx][yy]==0 && ch[xx][yy]==0){
				ch[xx][yy]=1;
				DFS(xx, yy);
				ch[xx][yy]=0;
			}		
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);
	int i, j;
	for(i=1; i<=7; i++){
		for(j=1; j<=7; j++){
			scanf("%d", &map[i][j]);
		}
	}
	ch[1][1]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}

    1번 문제   

    내가 풀이한 답   

 문제에 있는 예제는 다음과 같은 과정을 거친다. check 배열을 통해 이미 접근한 노드에 다시 접근하는 것을 방지하고 dfs 재귀 함수를 호출하였다.

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

int map[21][21], check[21], n, cnt=0;

void dfs(int v){
	if(v==n) cnt++;
	else {
		for(int i=1; i<=n; i++){
			if(map[v][i] == 1 && check[i] == 0){
				check[i] = 1;
				dfs(i);
				check[i] = 0;
			}
		}
	}
}

int main() {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	
	int m, i, a, b;
	cin >> n >> m;
	
	for(i=0; i<m; i++){
		cin >> a >> b;
		map[a][b] = 1;
	}
	
	check[1] = 1;
	dfs(1);
	
	cout << cnt;
	return 0;
}

 결과는 통과하였다.

    사이트의 답안   

<경로도 함께 출력하는 코드>
#include<stdio.h>	
int map[30][30], ch[30], cnt=0, n, path[30];
void DFS(int v, int L){
	int i, j;
	if(v==n){
		cnt++;
		for(j=0; j<L; j++){
			printf("%d ", path[j]);
		}
		puts("");
	}
	else{
		for(i=1; i<=n; i++){
			if(map[v][i]==1 && ch[i]==0){
				ch[i]=1;
				path[L]=i;
				DFS(i, L+1);
				ch[i]=0;
			}
		}
	}
}
				
int main(){
	freopen("input.txt", "rt", stdin);
	int m, i, j, a, b, c;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d", &a, &b);
		map[a][b]=1;
	}
	ch[1]=1;
	path[0]=1;
	DFS(1, 1);
	printf("%d\n", cnt);
	return 0;
}

    4번 문제   

    내가 풀이한 답   

 장애물이 없는 경우와 장애물이 있는 경우를 살펴보면 장애물이 없을 때 (1, 1)에서 (3, 3)까지 갈 수 있는 방법은 6가지이고 장애물이 있을 때에는 2가지이다. 

 한 칸 아래 또는 한 칸 오른쪽으로 갈 수 있으므로 점화식은 f(m, n) = f(m-1, n) + f(m, n-1)이다. 장애물 같은 경우는 갈 수 있는 경우의 수가 0이므로 0으로 설정해준다. 

#include <string>
#include <iostream>
#include <vector>
using namespace std;

int a[101][101];
int solution(int m, int n, vector<vector<int>> puddles) {
    for(int i=0; i<puddles.size(); i++){
        a[puddles[i][0]][puddles[i][1]] = -1;
    }
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(i==1 && j==1) a[i][j] = 1;
            else if(a[i][j] == -1) a[i][j] = 0;
            else a[i][j] = (a[i-1][j] + a[i][j-1])%1000000007;
        }
    }
    return a[m][n];
}

 결과는 통과하였다.