1. 처음 설계의 중요성 2. 문제 이해의 중요성 처음 문제가 잘 못되어 있어서 설계를 잘 못 해서 코드를 리팩토링 하려고 하니, 시간이 너무 많이 걸렸다. 어려운 문제가 아닌데, 문제를 잘 못 이해했으면, 처음부터 설계를 새로 하는 것이 좋습니다... 문제를 정독하고 처음 설계를 완벽하게 하는 것이 중요합니다. |
/* 1210 Ladder1 1540 시작합니다. */ #include <iostream> #include <algorithm> #include <memory.h> using namespace std; #define SIZE 100 // 100 struct point { int x, y, cnt; }que[SIZE*SIZE], start_store[SIZE]; int x, y, nx, ny; int dx[] = { 0,0,-1 }; // 동 서 남 int dy[] = { 1,-1,0 }; int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int ans; int front, rear; int cnt; int minVal = 212356789; int index1; int cnt_store[SIZE][2]; int index2; void problemIn() { for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { cin >> map[i][j]; } } } void init() { for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { visit[i][j] = 0; map[i][j] = 0; } } rear = front = -1; minVal = 2123456789; memset(que, 0, sizeof(que)); index1 = index2 = 0; ans = 0; cnt = 0; memset(cnt_store, 0, sizeof(cnt_store)); } void visit_init() { for (int i = 0; i < SIZE; i++) { for (int j = 0; j < SIZE; j++) { visit[i][j] = 0; } } minVal = 2123456789; memset(que, 0, sizeof(que)); } void bfs() { while (front != rear) { front++; x = que[front].x; y = que[front].y; cnt = que[front].cnt; if (x == 0) { cnt_store[index2][0] = cnt; cnt_store[index2][1] = y; index2++; return; } for (int i = 0; i < 3; i++) { nx = x + dx[i]; ny = y + dy[i]; if (nx >= 0 && ny >= 0 && nx < SIZE && ny < SIZE) { if (map[nx][ny] == 1 && visit[nx][ny] == 0) { visit[nx][ny] = 1; rear++; que[rear].x = nx; que[rear].y = ny; que[rear].cnt = cnt + 1; if (i != 2) { break; } } } } } } void solve() { for (int j = 0; j < SIZE; j++) { if (map[SIZE-1][j] == 1) { start_store[index1].x = SIZE - 1; start_store[index1].y = j; index1++; } } for (int i = 0; i < index1; i++) { front = rear = -1;
rear++; que[rear].x = start_store[i].x; que[rear].y = start_store[i].y; que[rear].cnt = 1; visit[SIZE - 1][start_store[i].y] = 1; bfs(); visit_init(); } for (int i = 0; i < index2; i++) { minVal = min(minVal, cnt_store[i][0]); } for (int i = index2 - 1; i >= 0; i--) { if (minVal == cnt_store[i][0]) { ans = cnt_store[i][1]; break; } } } int main() { for (int i = 0; i < 10; i++) { int tc; rear = front = -1; cin >> tc; problemIn(); solve(); cout << "#" << tc << " " << ans << endl; init(); } } |