1. 교착상태를 만들기 위해 포문을 사용할 때 주의해야 합니다. 내려가는 것은 아래서부터 검사하고, 올라가는 것을 위에서부터 검사하도록 합니다. 오께이. 2. 그리고 bfs 로 풀어서 교착상태를 세어줄 때는 교착 하는 조건을 정확하게 이해해주어야 합니다. |
/* 1220 Magnetic 1416 시작 1445 안에 설계 완료 후 코드 완성하기. 1. n번에 대해서 이동을 시킵니다. 이것은 단순하게 이중 포문 써서 하나씩 이동하도록 하겠습니다. 2. 교착상태의 갯수를 세도록 합니다. 세는 것 또한 열을 기준으로 샙니다. 1이나 2가 있으면, 오케이 하고, bfs 를 아래로만 해서 연속되는 것까지 이동하고, ++ 하나를 해주고, 다시 끝열까지 검사를 해서 또 있으면 ++ 를 해주면 됩니다. 오께이. 여기서는 bfs를 사용하면 됩니다. 아 같이 아래에도 1이 있으면 같이 내려갈 수 있는데 지금 코드는, 떨어져있는 경우만 있구나, 같이 1,1 있으면 같이 내려갈 수 있습니다. 1은 아래에서 위로 부터 검사하고, 2는 위에서 아래로부터 검사하면 되겠습니다. */ #include <iostream> #include <queue> #include <algorithm> using namespace std; #define SIZE 105 // 105 int map[SIZE][SIZE]; int visit[SIZE][SIZE]; int x, y, nx, ny; int n; int deadlockCnt; struct point { int x, y; }; queue<point> que; void problemIn() { cin >> n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> map[i][j]; } } } void init() { deadlockCnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { visit[i][j] = 0; } } } /* 순서를 행렬로 하는게 아니라, 열순으로 해야 하는군요. 하니씩 만 변동하도록 설계하려면 어떻게 해야 하는가? 현재것이 2인데, 아래가 1이면 break 해야 합니다. */ void bfs() {
while (!que.empty()) { x = que.front().x; y = que.front().y; que.pop();
for (int i = 0; i < 1; i++) { nx = x + 1; ny = y; if (nx < n && visit[nx][ny] == 0) { if (map[nx][ny] == 1 || map[nx][ny] == 2) { if (map[x][y] == 2 && map[nx][ny] == 1) break; visit[nx][ny] = 1; que.push({ nx,ny }); } } } } while (!que.empty()) que.pop(); deadlockCnt++; } /* 자성체가 1이라면 시간이 10초이므로, 괜찮습니다. 오께이. */ void solve() { // 1의 경우에는 아래에서 검사, 하고, 2의 경우에는 위에서 아래로 검사하겠습니다. for (int k = 0; k < n; k++) { for (int j = 0; j < n; j++) { for (int i = (n - 1); i >= 0; i--) { if (map[i][j] == 1) { if (i == (n - 1)) { map[i][j] = 0; } else if (i + 1 < n && map[i + 1][j] == 0) { swap(map[i][j], map[i + 1][j]); } } } for (int i = 0; i < n; i++) { if (map[i][j] == 2) { if (i == 0) { map[i][j] = 0; } else if (i - 1 >= 0 && map[i - 1][j] == 0) { swap(map[i][j], map[i - 1][j]); } } } } } for (int j = 0; j < n; j++) { for (int i = 0; i < n; i++) { if (map[i][j] == 1) { if (visit[i][j] == 0) { que.push({ i,j }); visit[i][j] = 1; bfs(); } } } } } int main() { for (int tc = 1; tc <= 10; tc++) { problemIn(); solve(); cout << "#" << tc << " " << deadlockCnt << endl; init(); } return 0; } |