백준 2178번 : 미로 탐색

문제 접근

---

1. 조건을 잘 확인하자.
   
     문제 자체는 BFS로 최단 거리를 구하는 간단한 문제다. 시작 칸과 도착 칸도 최단 거리에 포함되는지, 입력은 어떤 방식으로 되는지 등의 조건을 잘 확인하기만 하자.

 

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

 

문제 코드

---

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>

using namespace std;

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

	int N, M;
	string input;

	int maze[101][101];
	int dx[4] = { -1, 1, 0, 0 };
	int dy[4] = { 0, 0, -1, 1 };

	vector<vector<bool>> visited(101, vector<bool>(101, false));
	queue<tuple<int, int, int>> bfs;


	cin >> N >> M;

	for (int y = 1; y <= N; ++y)
	{
		cin >> input;

		for (int x = 1; x <= input.length(); ++x)
		{
			if (input[x - 1] == '1')
				maze[y][x] = 1;

			else
				maze[y][x] = 0;
		}
	}


	bfs.push(make_tuple(1, 1, 1));
	visited[1][1] = true;

	while (!bfs.empty())
	{
		int current_count = get<0>(bfs.front());
		int current_y = get<1>(bfs.front());
		int current_x = get<2>(bfs.front());

		bfs.pop();

		if (current_y == N && current_x == M)
			cout << current_count << '\n';

		for (int dir_idx = 0; dir_idx < 4; ++dir_idx)
		{
			if (current_y + dy[dir_idx] < 1 || current_y + dy[dir_idx] > N || current_x + dx[dir_idx] < 1 || current_x + dx[dir_idx] > M)
				continue;

			else if (maze[current_y + dy[dir_idx]][current_x + dx[dir_idx]] == 1 && !visited[current_y + dy[dir_idx]][current_x + dx[dir_idx]])
			{
				bfs.push(make_tuple(current_count + 1, current_y + dy[dir_idx], current_x + dx[dir_idx]));
				visited[current_y + dy[dir_idx]][current_x + dx[dir_idx]] = true;
			}
		}
	}


	return 0;
}

 

 

 

느낀 점

---

    실버 난이도의 그래프 문제는 대부분 개념을 활용할 수 있는지만 확인하는 것 같다. 슬슬 조금씩 난이도를 높여봐도 좋을 것 같다는 생각이 든다.

 

 

1. 좌표 조건을 문제와 맞추자.
   
     예전에 PS를 할 때는 문제의 좌표 조건이 0부터 시작하든 1부터 시작하든, 0에 맞춰서 코드를 작성했다. 이런 경우에는 문제의 다른 조건에서 빈틈이 생길 수 있으니 웬만하면 문제와 조건을 맞추도록 하자.