백준 14940번 : 쉬운 최단거리

문제 접근

---

1. BFS로 풀이한다.
   
     최단 거리는 별다른 특이사항이 없다면 BFS로 푸는 게 깔끔하다. 이 문제 역시 BFS로 단순하게 해결할 수 있는 문제였다.
   
   
2. 목표 지점에서부터 탐색한다.
   
     이번에는 시작점과 목표점이 N:1이어서 쉽게 목표점부터 탐색하자고 생각할 수 있었다. 만약 1:1이라고 하더라도 역으로 탐색을 하는 게 이로운 상황이 있으니 잘 살펴보고 설정하도록 하자.

 

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

14940번: 쉬운 최단거리

 

 

 

문제 코드

---

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

using namespace std;

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

	int n, m, row, col;
	int map[1001][1001] = { 0, };
	int ans[1001][1001] = { 0, };
	int dRow[4] = { 0, 1, 0, -1 };
	int dCol[4] = { -1, 0, 1, 0 };
	queue<tuple<int, int, int>> bfs;

	cin >> n >> m;

	for (row = 0; row < n; ++row)
	{
		for (col = 0; col < m; ++col)
		{
			cin >> map[row][col];

			if (map[row][col] == 2)
			{
				bfs.push(make_tuple(0, row, col));
			}

			else if (map[row][col] == 1)
			{
				ans[row][col] = -1;
			}
		}
	}

	while (!bfs.empty())
	{
		int distance = get<0>(bfs.front());
		int curRow = get<1>(bfs.front());
		int curCol = get<2>(bfs.front());
		bfs.pop();

		for (int i = 0; i < 4; ++i)
		{
			if (curRow + dRow[i] < 0 || curRow + dRow[i] >= n || curCol + dCol[i] < 0 || curCol + dCol[i] >= m)
				continue;

			if (ans[curRow + dRow[i]][curCol + dCol[i]] == -1 && map[curRow + dRow[i]][curCol + dCol[i]] == 1)
			{
				ans[curRow + dRow[i]][curCol + dCol[i]] = distance + 1;
				bfs.push(make_tuple(distance + 1, curRow + dRow[i], curCol + dCol[i]));
			}
		}
	}

	for (row = 0; row < n; ++row)
	{
		for (col = 0; col < m; ++col)
		{
			cout << ans[row][col] << " ";
		}
		cout << '\n';
	}

	return 0;
}

 

 

 

느낀 점

---

    문제를 풀다가 visual studio에 stack overflow 이슈가 생겨서 30분 정도 걸렸다.

 

 

Stack overflow

 

    처음에는 index를 잘못 접근한 곳이 있나 싶었는데, 찾아봐도 별다른 이상이 없어서 에러 코드로 검색해봤다.

 

    그 결과, 알고 보니 visual studio의 기본 stack 크기가 1MB인데 배열만 해도 map이랑 ans로 각각 4B(int 자료형 크기) * 1001 * 1001로 4,008,004B(약 4MB)씩 할당이 돼서 생긴 문제였다.

 

    이에 visual studio 기본 stack 크기를 약 100MB로 변경해서 앞으로 웬만하면 이런 일이 없도록 처리했다. 

 

 

[Project] - [(프로젝트 명) Properties] - [Linker] - [System] - [Stack Reserve Size] 조정으로 해결 가능

 

 

 

1. 에러 코드를 잘 살펴보자.
   
     나는 귀찮으면 대충 읽고 바로 구글링하는 경향이 있다. 물론 구글링 자체가 나쁜 건 아니지만, 생각하지 않는 건 앞으로의 성장에 부정적인 영향을 줄 수 밖에 없다. 앞으로는 귀찮더라도 한번쯤은 읽어본 뒤 왜 이런 일이 발생했을지 고민해보도록 하자.