-
[Algorithm] 백준 1600 말이 되고픈 원숭이 - C++, BFS쾌락없는 책임 (공부)/알고리즘 문제풀이 2022. 5. 16. 10:07반응형
#include <iostream> #include <queue> #include <algorithm> using namespace std; int moveY[] = { 0, 0, 1, -1 }; int moveX[] = { 1, -1, 0, 0 }; pair<int, int> horseMove[] = { {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {2, 1}, {1, 2} }; int k, w, h; int map[201][201]; bool visit[201][201][31]; bool IsOut(int y, int x){ if(x < 0 || y < 0 || x >= w || y >= h) return true; if(map[y][x] == 1) return true; return false; } bool SearchCount(){ queue<pair<pair<int, int>, pair<int, int>>> q; q.push({{0, 0}, {0, 0}}); while(!q.empty()){ int curK = q.front().first.first; int curCount = q.front().first.second; int curY = q.front().second.first; int curX = q.front().second.second; q.pop(); // if now on finish if(curY == h-1 && curX == w-1){ cout << curCount << '\n'; return true; } // can horse movement if(curK < k){ for(int i = 0; i < 8; i++){ int nextY = curY + horseMove[i].first; int nextX = curX + horseMove[i].second; if(IsOut(nextY, nextX)) continue; if(visit[nextY][nextX][curK+1]) continue; q.push({{curK+1, curCount+1}, {nextY, nextX}}); visit[nextY][nextX][curK+1] = true; } } // normal movement for(int i = 0; i < 4; i++){ int nextY = curY + moveY[i];; int nextX = curX + moveX[i]; if(IsOut(nextY, nextX)) continue; if(visit[nextY][nextX][curK]) continue; q.push({{curK, curCount+1}, {nextY, nextX}}); visit[nextY][nextX][curK] = true; } } return false; } int main(){ // init ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // input cin >> k; cin >> w >> h; for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ cin >> map[i][j]; } } if(!SearchCount()) cout << -1 << '\n'; }
NC 코테에서 쉬워보이는 BFS를 풀지 못했다는 아쉬움에 풀게 된 BFS 문제입니다. 기존의 4방향으로 이동하던 단순 BFS 와는 달리 8방향이 추가되어 총 12개 방향으로 갈 수 있게 된 문제입니다. 대신 추가된 8개 방향은 K번만 이동할 수 있어 이에 대한 제약조건이 필요한 문제였습니다.
queue<pair<pair<int, int>, pair<int, int>>> q;
일단 큐에 <현재 말처럼 이동한 횟수, 현재 이동 횟수>, <Y, X> 를 넣어주면서 계산을 했고
// can horse movement if(curK < k){ for(int i = 0; i < 8; i++){ int nextY = curY + horseMove[i].first; int nextX = curX + horseMove[i].second; if(IsOut(nextY, nextX)) continue; if(visit[nextY][nextX][curK+1]) continue; q.push({{curK+1, curCount+1}, {nextY, nextX}}); visit[nextY][nextX][curK+1] = true; } } // normal movement for(int i = 0; i < 4; i++){ int nextY = curY + moveY[i];; int nextX = curX + moveX[i]; if(IsOut(nextY, nextX)) continue; if(visit[nextY][nextX][curK]) continue; q.push({{curK, curCount+1}, {nextY, nextX}}); visit[nextY][nextX][curK] = true; }
이후 K횟수가 남았는지를 체크하면서 남았다면 말의 움직임을 해보고 아니면 하지 않는 방식으로 했습니다. 이렇게 기존 BFS 에 K 추가만 넣으면 쉽게 풀이할 수 있는 문제였습니다.
반응형'쾌락없는 책임 (공부) > 알고리즘 문제풀이' 카테고리의 다른 글
[Algorithm] 백준 16938 캠프 준비 - C++, DFS, 백트래킹 (0) 2022.05.18 [Algorithm] 백준 토마토 7569 - C++, BFS (0) 2022.05.18 [Algorithm] 프로그래머스 베스트 앨범 - C++, map, unordered_map (0) 2022.05.13 [Algorithm] 프로그래머스 신고 결과 받기 - C++, unordered_map, set (0) 2022.05.12 [Algorithm] 프로그래머스 위장 - C++, unordered_map (0) 2022.05.11