문제 URL : https://www.acmicpc.net/problem/16946
16946번: 벽 부수고 이동하기 4
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 �
www.acmicpc.net
문제 접근법 : 제목만 그냥 보자바자 bfs이용해서 벽부수고 도착점까지 이동하는 문제겠지 라고 생각했었는데
그게 아니더군요 문제 설명도 너무 짧아서 입력에대해 출력이 왜 저렇게 나오는지 이해하는데 오랜시간 분석해야했습니다. 하여간 문제 설명만 잘 이해해도 반은 해결하는건데 ㅠ.ㅠ
입력에대한 출력을 이해하고나서 문제가 너무 쉽게 풀렸습니다.
해당 1에대해서 bfs를 해당영역 이몇개인지 bfs를 돌리다보면
100프로 시간초과 일걸 예상하기때문에 그렇게는 안풀었습니다.
0이 좌우상하 연결되어있는 것들을 영역표시해주고 그영역의 넓이를 저장해줍니다.
그리고 1이 되어있는것들을 좌우상하 해당영역의 넓이들을 다더해주는 문제입니다.
여기서 핵심은 똑같은 영역을 2번이상 더해주면 안되니 영역에대한 번호를 표시해주는게 핵심이었습니다.
소스코드 :
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
//By 콩순이냉장고
#include<iostream>
#include<string>
#include<algorithm>
#include <vector>
#include <queue>
#include<unordered_set>
using namespace std;
int n, m;
char map[1002][1002];
int rec[1002][1002];
int visit[1002][1002];
int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
bool isrange(int y, int x)
{
if (1 <= y&&y <= n && 1 <= x&&x <= m)
return true;
return false;
}
void bfs(int y, int x,int color)
{
queue<pair<int, int>> q;
q.push({ y, x });
visit[y][x] = color;
vector<pair<int, int>> path;
path.push_back({ y, x });//경로를 저장
int cnt = 1;//넓이가 몇인지 체크
while (!q.empty()){
y = q.front().first;
x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++){
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && visit[ny][nx] == 0 && map[ny][nx] == '0')
{
visit[ny][nx] = color;
q.push({ ny, nx });
path.push_back({ ny, nx });
cnt++;//넓이가 1씩늘어남
}
}
}
for (int i = 0; i < path.size(); i++)
{
rec[path[i].first][path[i].second] = cnt;//해당경로들 전부 그넓이가 얼마인지 저장
}
}
int main(void)
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> map[i][j];
}
}
int color = 1;//영역을 따저주는 변수 1부터 시작
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (visit[i][j] == 0 && map[i][j] == '0'){
bfs(i, j,color++);
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (map[i][j] == '1')
{
int cnt = 1;
unordered_set<int> usecolor;//같은영역 2번이상 더할수없게
for (int k = 0; k < 4; k++)
{
int ny = i + dy[k];
int nx = j + dx[k];
if (usecolor.count(visit[ny][nx]) == 0){//같은영역을 또다시 더하지 않게 한번만 더하게하기
cnt += rec[ny][nx];
usecolor.insert(visit[ny][nx]);
}
}
cout << cnt % 10;
}
else
cout << 0;
}
cout << "\n";
}
}
|
cs |
모르는 점 혹은 궁금한점 ,혹은 제가 틀린부분이 있다면 언제든 댓글을 이용해주시길 부탁드립니다.
'백준' 카테고리의 다른 글
| 백준 1781 컵라면 (0) | 2020.08.25 |
|---|---|
| 백준 16985 Maaaaaaaaaze (0) | 2020.08.25 |
| 백준 1202 보석 도둑 (0) | 2020.08.24 |
| 백준 17299 오등큰수 (0) | 2020.08.13 |
| 백준 11576 Base Conversion (0) | 2020.08.13 |
