어흥
[백준 17086] 아기 상어 2 (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/17086
1. 주의할 점
- BFS로 접근하되, 시작지점을 아기상어의 위치로 잡는다
2. 구현
- 모든 Check[][]값을 MAX로 초기화한다
- 아기상어가 위치한 곳을 큐에 넣고, Check[][]값을 0으로 설정한다
- 8방향 탐색을 통해 이동하려는 곳의 Check[][]값이 현재 이동한 거리(CV)+1보다 크다면 이동하고 Result를 CV+1와 비교하여 큰 값을 갖도록 한다
#define MAX 987654321
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
int x, y, val;
};
info tmp;
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
int arr[50][50];
int check[50][50];
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int row, col;
cin >> row >> col;
queue<info> q;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
cin >> arr[i][j];
check[i][j] = MAX;
if (arr[i][j] == 1) {
tmp.x = j;
tmp.y = i;
tmp.val = 0;
q.push(tmp);
check[i][j] = 0;
}
}
}
int result = 0;
while (!q.empty()) {
int cx = q.front().x;
int cy = q.front().y;
int cv = q.front().val;
q.pop();
for (int i = 0; i < 8; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx >= 0 && ny >= 0 && nx < col&&ny<row && check[ny][nx]>cv + 1) {
check[ny][nx] = cv + 1;
tmp.x = nx;
tmp.y = ny;
tmp.val = cv + 1;
q.push(tmp);
result = max(result, cv + 1);
}
}
}
cout << result;
system("pause");
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 1981] 배열에서 이동 (C++) (0) | 2020.05.22 |
---|---|
[백준 1967] 트리의 지름 (C++) (0) | 2020.05.22 |
[백준 14003] 가장 긴 증가하는 부분 수열 5 (C++) (0) | 2020.05.17 |
[백준 12738] 가장 긴 증가하는 부분 수열 3 (C++) (0) | 2020.05.17 |
[백준 12015] 가장 긴 증가하는 부분 수열 2 (C++) (0) | 2020.05.17 |
Comments