[백준] 14940. 쉬운 최단거리 (C++)

Key

출력 조건과 출력되는 형태를 잘 봐야한다.

시작 지점이 항상 [0][0]인 것은 아니다.

그리고 항상 2차원 배열 문제에서 실수가 많이 나오는 부분인데, arr[x][y]에서 x는 행이고 y는 열이라는 것을 헷갈리면 안된다. (x,y)가 아니다!!

 

Idea

시작 지점에서 bfs를 진행하고, 사방에 만약 1이고 방문하지 않은 칸이 있다면 현재 지점+1 값으로 바꿔준다.

보통 이런 문제는 bool 타입 visited 배열을 따로 만들어 방문 여부를 판단하는데, 나는 입력을 받을 때 입력값-2로 저장했다. 이렇게 하면 저장된 값이 유니크해져서 방문 배열을 만들지 않고도 방문 여부를 체크할 수 있다.

 

0이 시작점이고, 갈 수 있는 땅은 -1, 갈 수 없는 땅은 -2가 된다.

따라서 범위를 넘지 않고 값이 -1이면 변경 가능한 상태라는 것이다.

입력값을 그대로 쓰게 된다면 목표지점에서 거리가 1인 땅과 입력값이 1인 땅이 구분되지 않아 방문 배열을 써야한다.

 

참고로 나는 로직이 완벽하다고 생각했는데 3%에서 한 번 틀리고, 90%에서 또 한번 틀렸다. 몇십분동안 이유를 찾고 허탈해졌다.. 질문 게시판을 보니 많은 분들이 이 부분에서 많이 틀리더라.

코드 구조만 참고하고 틀린 부분은 혼자 해결하고 싶은 분들을 위해 틀린 이유는 접은 글로 쓰겠다.

3%에서 틀린 이유 : 출력할 때 숫자 사이에 공백을 안 넣어줬음

90%에서 틀린 이유 : 범위를 체크할 때 N, M을 거꾸로 썼다. arr[x][y]에서 x는 행, y는 열이라는 것을 잊지 말자... 좌표 (x,y)가 아니다.

 

Code

#include <iostream>
#include <queue>
using namespace std;

int arr[1001][1001] = { 0, };
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
int bfs_cnt = 0;
int N = 0, M = 0;

queue<pair<int,int>>q;

bool isRange(int x, int y) {
	// N,M 바꿔써서 90퍼에서 틀림
	if (x < M && x >= 0 && y < N && y >= 0) return true;
	return false;
}

void bfs() {

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
				int nextX = dx[i]+x;
				int nextY = dy[i]+y;

				// 범위를 넘지 않고 -1이면 값 변경, 큐에 넣기
				if (isRange(nextX, nextY) && arr[nextX][nextY] == -1) {
					arr[nextX][nextY] = arr[x][y] + 1;
					q.push(make_pair(nextX, nextY));
				}
			}
	}

	
}

int main() {
	int input;

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> input;
			if (input == 2) {
				q.push(make_pair(i, j));
			}
			arr[i][j] = input - 2;
		}
	}

	bfs();

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			// 원래 갈 수 있는 땅이지만 도달 못했을 경우 -1 출력
			if (arr[i][j] == -2) cout << "0 ";
			else if (arr[i][j] == -1) cout << "-1 ";
			else cout << arr[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}