[백준 2589번 C/C++] 보물선
[백준 2589번 C/C++] 보물선

https://www.acmicpc.net/problem/2589
2589번: 보물섬
보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서
www.acmicpc.net
해결전략
너비우선탐색 BFS
정답 코드
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int r, c; vector<vector<char>> v; int answer; void BFS(int startY, int startX) { vector<vector<int>> ch(r, vector<int>(c, -1)); queue<pair<int, int>> Q; Q.push({ startY, startX }); ch[startY][startX] = 0; while(!Q.empty()) { int y = Q.front().first; int x = Q.front().second; Q.pop(); for(int i = 0; i < 4; i++){ int ny = y + dirY[i]; int nx = x + dirX[i]; if (ny < 0 || r <= ny || nx < 0 || c <= nx || v[ny][nx] == 'W') continue; if (ch[ny][nx] == -1 && v[ny][nx] == 'L') { Q.push({ ny, nx }); ch[ny][nx] = ch[y][x] + 1; answer = max(answer, ch[ny][nx]); } } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> r >> c; v.resize(r, vector<char>(c)); for(int y = 0; y < r; y++){ for (int x = 0; x < c; x++) { cin >> v[y][x]; } } for (int y = 0; y < r; y++) { for (int x = 0; x < c; x++) { if (v[y][x] == 'L') BFS(y, x); } } cout << answer; return 0; }
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 15864번 C/C++] 사다리 조작 (1) | 2024.04.19 |
---|---|
[백준 6087번 C/C++] 레이저 통신 (0) | 2024.04.16 |
[백준 3687번 C/C++] 성냥개비 (0) | 2024.04.14 |
[백준 14890번 C/C++] 경사로 (0) | 2024.04.13 |
[백준 8980번 C/C++] 택배 (0) | 2024.04.10 |
댓글
이 글 공유하기
다른 글
-
[백준 15864번 C/C++] 사다리 조작
[백준 15864번 C/C++] 사다리 조작
2024.04.19[백준 15864번 C/C++] 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답 코드 #include using namespace std; int n, m, h; int ch[31][11]; bool Cal() { for (int start = 1; start > n >> m >> h; for (int i = 0; i < m; i++) { int y, x; cin >> y >> x; … -
[백준 6087번 C/C++] 레이저 통신
[백준 6087번 C/C++] 레이저 통신
2024.04.16[백준 6087번 C/C++] 레이저 통신 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 해결전략 너비우선탐색 BFS 정답코드 #include #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int w, h;// w: 맵의 너비, h: 맵의 높이 int answer = 987654321;// 최소 거울 … -
[백준 3687번 C/C++] 성냥개비
[백준 3687번 C/C++] 성냥개비
2024.04.14[백준 3687번 C/C++] 성냥개비 https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 해결전략 구현 동적계획법 Dynamic Programming, DP 정답코드 #include #include #include using namespace std; int t; // 테스트 케이스의 개수 int n; // 성냥개비의 개수 // int num[10] = { 2, 5, 5, 4, 5, 6, 3, 7, 6, 6 }; // 각 숫자를 만드는데 필요한 성냥개비… -
[백준 14890번 C/C++] 경사로
[백준 14890번 C/C++] 경사로
2024.04.13[백준 14890번 C/C++] 경사로 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 해결전략 구현 정답 코드 #include #include using namespace std; int n, l; // n: 지도의 크기, l: 경사로의 길이 int answer; vector v; bool RoadCheckY(int y) // y번째 행에 대해 경사로를 설치할 수 있는지 검사 { vector ch(n, vector(n, false)); for (int i = 0; …
댓글을 사용할 수 없습니다.