미로 탐색

아 일단 최대 최소 확인하고 시간제한 확인하고

문제를 이해를 함. 아 일단 DFS로 풀어야겟다? 해서 풀다가 TC 넣어보고 뭔가 이상해서 문제를 다시 읽었더니 문제에서 " 최소의 칸 수 " 를 구하라고 한다.

즉, 처음에는 DFS로 구했는데 BFS라는 것을 깨달았다.

그래서 DFS코드와 BFS코드 둘다 작성함.

다만 주의해야할 점은

0일 경우 못가니까 Cango함수에서

arr[y][x] == 0일 경우 false를 return 하여야 한다.

DFS

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define endl "\n"

int n, m;
int arr[102][102];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};
int visited[102][102];

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= m || arr[y][x] == 0) return false;
	return true;
}

int cnt = 0;
void DFS(int y, int x)
{
	visited[y][x] = ++cnt;
	
	for (int i = 0; i < 4; ++i)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (Cango(ny, nx) == false) continue;
		if (visited[ny][nx]) continue;
		DFS(ny, nx);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	
	string str;
	for (int i = 0; i < n; ++i)
	{
		cin >> str;

		for (int k = 0; k < str.size(); ++k)
		{
			string s = str.substr(k , 1);
			int a = atoi(s.c_str());
			arr[i][k] = a;
		}
		int b = 10;
	}
	
	DFS(0, 0);
	cout << visited[n - 1][m - 1] << endl;

	return 0;
}

BFS

아래 코드가 맞는 코드이다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define endl "\n"

int n, m;
int arr[102][102];
int dy[4] = {0, 1, 0, -1};
int dx[4] = {-1, 0, 1, 0};
int visited[102][102];
queue<pair<int, int>> q;

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= m || arr[y][x] == 0) return false;
	return true;
}

void BFS(int y, int x)
{
	visited[y][x] = 1;
	
	q.push({y, x});
	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; ++i)
		{
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (!Cango(ny, nx)) continue;
			if (visited[ny][nx]) continue;
			visited[ny][nx] = visited[y][x] + 1;
			q.push({ny, nx});
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	
	string str;
	for (int i = 0; i < n; ++i)
	{
		cin >> str;

		for (int k = 0; k < str.size(); ++k)
		{
			string s = str.substr(k , 1);
			int a = atoi(s.c_str());
			arr[i][k] = a;
		}
		int b = 10;
	}

	BFS(0, 0);
	
	cout << visited[n - 1][m - 1] << endl;

	return 0;
}

코드 분석 및 수정

Cango 함수에서

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= m || arr[y][x] == 0) return false;
	return true;
}

```할부분

지금 입력으로 110111이런식으로 입력을 받는데 
cin 함수는 공백(" ")을 기준으로 입력을 받기때문에 이중 for문에서 cin >> arr[i][j]이런식으로 하면 입력을 못받기 때문에

```cpp
for (int i = 0; i < n; ++i)
{
	cin >> str;

	for (int k = 0; k < str.size(); ++k)
	{
		string s = str.substr(k , 1);
		int a = atoi(s.c_str());
		arr[i][k] = a;
	}
	int b = 10;
}

일단 이런식으로 입력을 받았는데 바꿀 부분이 있을까??

입력이 따닥따닥 붙은 경우 ❗

지금 나처럼

for (int i = 0; i < n; ++i)
{
	cin >> str;

	for (int k = 0; k < str.size(); ++k)
	{
		string s = str.substr(k , 1);
		int a = atoi(s.c_str());
		arr[i][k] = a;
	}
	int b = 10;
}

이런식으로 하는 방법도 있을 테고

#include <bits/stdc++.h>
using namespace std;
int a[10][10], n, m;
int main()
{
  cin >> n >> m;
  for(int i = 0; i < n; i++)
  {
  	for(int j = 0; j < m; j++)
    {
  		scanf("%1d", &a[i][j]);
	}
  }
	return 0;
}

이렇게 앞에 1을 붙이면 “한자리의 int”만을 받겠다라는 뜻이 되어 받을 수 있습니다.
0과 1은 int고 한자리씩 받으면 되니 이렇게 받을 수 있는 셈이죠.

OverFlow 체크 ❗❗❗

Cango 함수에서

bool Cango(int y, int x)
{
	if (y < 0 || y >= n || x < 0 || x >= m || arr[y][x] == 0) return false;
	return true;
}

if 문에서 이런식으로 확인을 해주고있는데

arr[y][x] == 0이 제일뒤에 있는 상황이다.

근데 만약

if (arr[y][x] == 0 ||y < 0 || y >= n || x < 0 || x >= m)

이런식으로 제일 앞에 arr[y][x]해버리면 되나 안되나?

절대안됨! 왜냐하면 Cango함수는 nextY, nextX 좌표를 인자로받는데 인덱스 범위를 벗어나는지 아닌지부터 확인을 해야하기 때문이다.

만약 arr[y][x]에서 y, x가 인덱스를 벗어나면 Index Out Of Range발생하기 때문에

먼저 y < 0 || y >= n || x < 0 || x >= m
이런 조건들을 확인을 해주어야한다.

if문 조건체크는 앞에있는거 부터 순서대로 하기 때문이다.