일단 생각한대로 코딩을 하면 풀린다. 이것 큐2개 넣어서, 처음에 케이에 대해서 깎은 맵을 형성한 다음에, 오께이. 다른 사람들 것을 보니 dfs 로 풀이가 많은 것 같다. 깊이 부터 파는 것. 이 문제의 원래 핵심이 아니였을까? bfs 로 풀 경우, visit 맵에 대해서 계속해서 관리를 해주어야 하고, 가장 멀리 갔을 때의 깊이를 찾아주어야 한다. 다음에 이런 문제를 만났을 때는 dfs 로 풀이를 해보도록 하겠습니다. 그리고 문제를 유심히 읽어서, 가능한 변수에 대해서 꼭 알아야 합니다. 이번에 맵의 K만큼이 아니라 최대 K 만큼 팔 수 있는 것이므로, 이것에 대해서 코딩을 해주어야 합니다. 48개에서 막혀서 당황하지 말고, 문제를 반드시 잘 읽고, 코드도 제대로 다시 읽어보도록 합니다. 만약에 이것을 찾지 못했더라면, dfs로 다시 짜는데 시간이 소요 되었을 것입니다. 이것이 시험에도 반복되면 절대 안됩니다. 처음에 문제를 정독하기. 문제를 이해했더라도, 입력 출력 하는 부분 모두 읽어야 놓치지 않습니다. |
/* 1118 등산로 조성 왜 같이 쓰면 답이 안나오지? */ #include <iostream> #include <queue> // 깎은 변수 인지 아닌지를 계산 #include <algorithm> using namespace std; #define SIZE 9 // 9 int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int nx, ny, x, y; int dx[] = { 0,0,1,-1 }; int dy[] = { 1,-1,0,0 }; struct points { int x, y; }; int ans; int top; int N, K; queue<points> que; queue<points> top_store; void problemIn() { cin >> N >> K; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> map[i][j]; } } } void map_init() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) map[i][j] = 0; } void visit_init() { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) visit[i][j] = 0; } /* bfs를 돌려서 내려갈 수 있는 길을 찾아보도록 하겠습니다. visit 함수를 만들어야겠습니다. bfs 와 dfs 둘다 가능할 것 같은데? 어떤 것이 더 좋은지?? 일단은 bfs 를 구현하기가 더 쉬우니 bfs 로 해보도록 하겠습니다. 비지트 함수를 만드는데, 비지트에 간 거리를 넣으면 되겠습니다. 지금 알고리즘은 0일때만 가는데, 순서가 중요하므로, 이것은 BFS로 안풀릴 것 같습니다.? 아니면 조건을 바꾸어서, 갔던길도 갈 수 있도록? */ void bfs() {
while (!top_store.empty()) { visit_init(); x = top_store.front().x; y = top_store.front().y; top_store.pop(); que.push({ x,y }); visit[x][y] = 1; while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop(); for (int i = 0; i < 4; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < N && ny < N) { // 일단 맵에서 벗어나지 않고, if (map[nx][ny] < map[x][y]) { visit[nx][ny] = visit[x][y] + 1; que.push({ nx,ny }); // 계속 돌리기는 하는데 거리는 어떻게 셀 수 있을까? } } } } // 가장 긴 거리를 간 것을 저장합니다. for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { ans = max(ans, visit[i][j]); } } } } void find_way() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { top = max(top, map[i][j]); // top 을 저정하는 큐가 하나 있어야 겠습니다. } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (top == map[i][j]) top_store.push({ i,j }); } } bfs(); } // 안깎은 맵에 대해서도 조사를 해야하는가? 일단 아니라고 생각되서, 패스 void solve() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k <= K; k++) { map[i][j] -= k; find_way(); // 하나씩 깎은맵 map[i][j] += k; } } } } int main() { int T; cin >> T; for (int tc = 1; tc <= T; tc++) { map_init(); problemIn(); solve();
cout << "#" << tc << " " << ans << endl; ans = 0; top = 0; } return 0; }
|