오랜만에 알고리즘 문제를 풀어서 그런지 문제를 제대로 안읽어서 엄청 틀렸다
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번
- 문제를 만든 사람: semteo04