일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 1796
- 자료구조
- 9996
- TDD란?
- 테스트주도개발
- 13459
- dp
- 백준
- LOLIN D32
- 백준 2133
- 2623
- TDD
- c++
- Vite 사용 이유
- 적두트리
- RBT
- ESP32
- 3XN 타일링
- WebRTC란
- 데이터 링크 계층
- 페이지교체알고리즘
- 구슬탈출
- mediastream
- 풀이
- 구현
- 메모리계층
- stl
- REACT
- tfjs
- OpenVidu
- Today
- Total
그냥 블로그
[C++/백준] 16724 피리 부는 사나이 본문
https://www.acmicpc.net/problem/16724
16724번: 피리 부는 사나이
첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주
www.acmicpc.net
[ 아이디어 구상 ]
일단 처음에 문제를 읽고 시뮬레이션이라고 생각했다.
말을 좀 어렵게 써놨는데 예시 그림?을 보면서 생각해보면 결국 구하는 것이 말이 'SAFE ZONE'이지 연결되지 않은 땅의 개수인 걸 알 수 있었다.
구하는 것 : 연결되지 않은 땅 개수
=> BFS 아님 DFS로 구하면 되겠구나를 알 수 있었다.
그리고 방향으로 생각해 보면 연결되는 건 두 가지 인데,
1) 내가 서 있는 땅에서 가야하는 방향
2) 나한테 들어오는 방향의 땅
이 두가지를 고려해주면 된다.
1의 경우 쉬운데 2는 그럼 어떻게 알 수 있을까??????
내가 서 있는 땅으로 들어오는 방향의 땅들을 탐색할 때, 항상 그렇듯 4방향 배열로 구해줄 거라고 생각하면
초록색 : 내가 탐색하는 dy[] = {1, -1, 0, 0} dx[] = {0, 0, -1, 1}
검은색 : 나한테 들어오는 경우의 방향 인데
내가 있는 좌표를 (2,2) 라고 뒀을 때,
위쪽 좌표(1,2)의 방향을 확인했을 때 dy[i] = -1, dx[i] = 0 이 되고
그 방향에서 내가 있는 좌표와 연결되기 위해 적혀있어야 할 방향은 D(1,0)이다.
즉 서로 x -1을 해서 같아지는 방향이라는 것이다 ㅇㅇ .
이걸 떠올린 다음 손 코딩을 들어갔다. 기본적인 BFS를 사용하면 되는데
1) 내가 가야하는 다음 좌표
2) 나한테 들어오는 좌표
두 가지 경우 모두 고려해서 짜줬다.
그리고 입력이 UDLR 처럼 문자로 들어와서 그냥 if문을 써도 금방 될 거 같긴 하지만,,,
map 자료형을 써서 편하게 하기로 했다.
[ 문제 풀이 ]
#include<iostream>
#include<string>
#include<queue>
#include<map>
using namespace std;
int N, M;
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,-1,1 };
vector<string> board;
vector<vector<int>> visited;
map<char, pair<int, int>> m; // UDLR 검색.
void BFS(int y, int x){
queue<pair<int, int>> q;
q.push({ y,x });
visited[y][x] = 1;
while (!q.empty()) {
int y = q.front().first;
int x = q.front().second;
q.pop();
// 내가 가야하는 좌표는 넣음
int gy = y+m[board[y][x]].first;
int gx = x+m[board[y][x]].second;
if (!visited[gy][gx]) {
visited[gy][gx] = 1;
q.push({ gy,gx });
}
// 나한테 들어오는 방향의 좌표 넣음
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) continue;
if (visited[ny][nx]) continue;
// 탐색한 방향의 반대가 되는 경우 넣음
if (m[board[ny][nx]].first == -1 * dy[i] && m[board[ny][nx]].second == -1 * dx[i]) {
q.push({ ny,nx });
visited[ny][nx] = 1;
}
}
}
}
int main() {
cin >> N >> M;
cin.ignore();
m['U'] = { -1,0 };
m['D'] = { 1,0 };
m['L'] = { 0,-1 };
m['R'] = { 0,1 };
for (int i = 0; i < N; i++) {
string s;
cin >> s;
board.push_back(s);
vector<int> v(M);
fill(v.begin(), v.end(), 0);
visited.push_back(v);
}
int ans = 0;
for (int y = 0; y < N;y++) {
for (int x = 0; x < M; x++) {
if (visited[y][x]) continue;
BFS(y, x);
ans += 1;
}
}
std::cout << ans;
}
++
다른 포스팅을 좀 찾아보니까 DFS로 많이 푸는 것 같다.
이게 (밖으로 나가는 경우가 없다) 라는 조건에 의해서 무조건 사이클이 생기고 그렇게 되면 그 사이클 개수를 찾으면 된다고 함..!! visted[y][x] = 1이 되는 경우에 사이클이 생긴다고 보고 종료하는 방법인 것 같다
[고찰]
풀면서 실수가 좀 많았따... 손코딩 + 1차 코딩까지 30분? 정도가 걸렸는데 잔실수에,,,
아직도 언어에 안 익숙한지 헷갈리는 게 많아서 시간도 오래걸리고 디버깅도 계속 해줬다.
일단... 방향을 잘못 생각해줘서 한번 틀렸었다. U = -1,0 인데 뇌빼고 사는 듯 1,0으로 해줘서 으휴 ㅋㅋ 코딩 접어라
두번째로 입력할 때 뻘짓하다가 틀렸는데.. 여기서 진짜 뭐 떄문에 틀린지도 모르겠어서 결국 chatGPT를 사용했다.
입력이 제대로 안되면..ㅠㅠ
문자열이라고 또 getline으로 뻘짓하다가 오류가 생긴거 였는데.. 사실 공백이 없어서 그냥 cin으로 받으면 됨
for 문 안에 cin.ignore()랑 getline을 순차적으로 써서 생긴 오류였다.
이게 ignore가 단순히 개행문자 포함인 줄 알았는데 위 사진처럼 3을 입력 받은 후 cin.ignore(4)를 하면 그 뒤에 들어오는 것까지 다 지워진다고 한다.
그래서 내가 받은 입력에 첫번째 문자가 계속 지워졌고 ㅠㅠ ...
잘하자..
추가로 int 배열 범위가 계속 헷갈리기도 하고 잘 모르겠는데 한 백만까지는 버티는 듯
'C++ > 백준' 카테고리의 다른 글
[ 백준 / C++ ] 구슬 탈출 (1) | 2024.02.11 |
---|---|
[ C++ / 백준 ] 1796 신기한 키보드 (0) | 2024.02.01 |
[C++/백준] 고층 건물 (0) | 2024.01.14 |
[C++/백준] 20040 사이클 게임 (1) | 2024.01.13 |
[C++/백준] 1647 도시분할계획 (1) | 2024.01.07 |