BOJ 14940 쉬운 최단거리

 

오랜만에 알고리즘 문제를 풀어서 그런지 문제를 제대로 안읽어서 엄청 틀렸다

n m 입력 받고 습관적으로 정사각형인줄알고 nn 인줄알고 풀어서 엄청 틀렸다

문제 읽기도 매우 중요하다.

문제 풀이는 간단하게 BFS 를 사용하여 풀면 끝난다.

엄청 긴 if 문을 나누자니 tap 이 엄청 많아지고, 이어쓰자니 엄청 길어져서 읽기 불편했는데,

번뜩 아래와 같이 가독성 좋고 짧은 코드를 써보니 매우 좋았다. 역시 continue 는 마법인거같다.

// 1번 안
if(1 <= cx && cx <= n && 1 <= cy && cy <= m && mmap[cx][cy] != 0 && check[cx][cy] == false){
    // 로직이 들어가는 부분
}

//2번 안

if (1 <= cx && cx <= n && 1 <= cy && cy <= m){
    if (mmap[cx][cy] != 0 && check[cx][cy] == false){
    	//로직이 들어가는 부분
	}
}

//3번 안

if (!(1 <= cx && cx <= n && 1 <= cy && cy <= m)) continue;
if (!(mmap[cx][cy] != 0 && check[cx][cy] == false)) continue;
// 로직이 들어가는 부분
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;
#define INF 1234567890

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int mmap[1005][1005];
bool check[1005][1005];
int result[1005][1005];
int x, y;

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

	int n, m;
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mmap[i][j];
			if (mmap[i][j] == 2)
				x = i, y = j;
		}
	}
	

	queue<pair<int, int>> que;
	que.push({ x, y });
	check[x][y] = true;

	while (!que.empty()) {
		pair<int, int> cur_node = que.front();
		que.pop();
		for (int i = 0; i < 4; i++) {
			int cx = cur_node.first + dx[i];
			int cy = cur_node.second + dy[i];
			if (!(1 <= cx && cx <= n && 1 <= cy && cy <= m)) continue;
			if (!(mmap[cx][cy] != 0 && check[cx][cy] == false)) continue;
			
			check[cx][cy] = true;
			result[cx][cy] = result[cur_node.first][cur_node.second] + 1;
			que.push({cx, cy});
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (check[i][j] == false && mmap[i][j] != 0)
				cout << -1 << ' ';
			else
				cout << result[i][j] << ' ';

		}
		cout << "\n";
	}

	return 0;
}


쉬운 최단거리

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 261 128 104 49.524%

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2≤n≤1000, 2≤m≤1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 벽인 위치는 0을 출력하고, 원래 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

예제 입력 1

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력 1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

출처

University > 서강대학교 > 2017 Sogang Programming Contest - Master F번