[SW Expert] #1226 S/W 문제해결 기본 7일차 - 미로1

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

SW Expert Academy

1. 해결방법

dfs를 사용하여 방문여부를 체크하고, 더불어 array의 값이 3일때를 체크하는 방식을 사용하였다.

방문여부를 체크할 bool array가 dfs재귀함수 호출전에 체크해줘야한다는 주의사항이 있다.

---

2. 코드

#include <string.h>
#include <iostream>
using namespace std;
int num = 0;
int ary[16][16];
int bo[16][16] = { 0 };
int result = 0;
int dx[4] = { -1, 1 ,0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void dfs(int x, int y) {
    bo[1][1] = 1;
	if (ary[x][y] == 3) {
		result = 1;
	}
	else {
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || ny < 1 || nx >= 14 || ny >= 14 || ary[nx][ny] == 1 || bo[nx][ny]){
                continue;
            }
			else{
                                bo[nx][ny] = 1;
                dfs(nx, ny);
            }
        }
	}
}
int main()
{
	for (int i = 0; i < 10; i++) {
		scanf("%d", &num);
		memset(bo, 0, sizeof(bo));
		for (int m = 0; m < 16; m++) {
			for (int n = 0; n < 16; n++) {
				scanf("%1d", &ary[m][n]);
			}
		}
		result = 0;
		dfs(1, 1);

		cout << "#" << num << " " << result << endl;
	}
}