문제
접근 방법
코드를 줄이는 습관을 들여야겠다. 문제는 모든 방향에 대해서 10번을 수행한뒤 안되면 -1을 출력하면 된다.
- 노드 구조체를 만들어 빨간색, 파란색 구슬을 관리한다.
- 각 방향 별로 구슬을 벽까지 이동시키고 빨간 구슬과 파란 구슬의 위치를 봐서 상관 관계를 구현한다.
- 파란 구슬과 빨간 구슬이 동시에 들어갔을 경우를 예외처리한다.
- 노드 객체 안에 cnt를 증가시키고 변경된 위치를 큐에 집어 넣는다.
- cnt가 10보다 크거나 작으면 -1을 출력한다.
코드
#include <iostream> #include <queue> using namespace std; struct node { int redR; int redC; int blueR; int blueC; int redGoal = 0; int blueGoal = 0; int cnt = 0; }; int N, M; int map[11][11]; queue q; int main() { cin >> N >> M; char c; node n; for(int i = 0; i < N; i ++) { for(int j = 0; j < M; j ++) { cin >> c; if(c == '#') { // 벽은 -1로 저장 map[i][j] = - 1; } else if (c == '.') { // 길은 0으로 저장 map[i][j] = 0; } else if(c == 'O') { // 출구는 1로 저장 map[i][j] = 1; } else if(c == 'R') { // 빨간 구슬 위치 저장 n.redR = i; n.redC = j; } else { // 파란 구슬 위치 저장 n.blueR = i; n.blueC = j; } } } // 큐에 삽입 q.push(n); while(!q.empty()){ // cnt가 10보다 크거나 같으면 탈출 if(q.front().cnt >= 10) break; // 4방향에 대해서 큐에 삽입 for (int dir = 0; dir < 4; dir++) { // 북 if (dir == 0) { node temp = q.front(); // 새롭게 위치한 빨간 구슬과 파란 구슬의 row값 int redNR = temp.redR; int blueNR = temp.blueR; // 빨간 구슬 벽으로 이동 while (map[redNR - 1][temp.redC] != -1) { // 출구라면 이동을 중단하고 탈출 if (map[redNR - 1][temp.redC] == 1) { temp.redGoal = 1; break; } redNR--; } // 파란 구슬 벽으로 이동 while (map[blueNR - 1][temp.blueC] != -1) { if (map[blueNR - 1][temp.blueC] == 1) { temp.blueGoal = 1; break; } blueNR--; } // 빨간 구슬과 파란 구슬의 위치가 같으면 이전 위치에서 상관 관계를 봐 위치를 조정 if (temp.blueC == temp.redC && redNR == blueNR) { if (temp.redR < temp.blueR) { blueNR++; } else { redNR++; } } // 빨간 구슬만 골인 했다면 정답 출력 if (temp.blueGoal == 0 && temp.redGoal == 1) { cout << temp.cnt + 1; return 0; } // 빨간 구슬과 파란 구슬이 아직 골인이 아니라면 cnt를 증가시키고 위치를 바꾼 다음 큐에 삽입 if (temp.blueGoal == 0 && temp.redGoal == 0) { temp.cnt++; temp.blueR = blueNR; temp.redR = redNR; q.push(temp); } } // 남 else if (dir == 1) { node temp = q.front(); int redNR = temp.redR; int blueNR = temp.blueR; while (map[redNR + 1][temp.redC] != -1) { if (map[redNR + 1][temp.redC] == 1) { temp.redGoal = 1; break; } redNR++; } while (map[blueNR + 1][temp.blueC] != -1) { if (map[blueNR + 1][temp.blueC] == 1) { temp.blueGoal = 1; break; } blueNR++; } if (temp.blueC == temp.redC && redNR == blueNR) { if (temp.redR < temp.blueR) { redNR--; } else { blueNR--; } } if (temp.blueGoal == 0 && temp.redGoal == 1) { cout << temp.cnt + 1; return 0; } if (temp.blueGoal == 0 && temp.redGoal == 0) { temp.cnt++; temp.blueR = blueNR; temp.redR = redNR; q.push(temp); } } // 서 else if (dir == 2) { node temp = q.front(); int redNC = temp.redC; int blueNC = temp.blueC; while (map[temp.redR][redNC - 1] != -1) { if (map[temp.redR][redNC - 1] == 1) { temp.redGoal = 1; break; } redNC--; } while (map[temp.blueR][blueNC - 1] != -1) { if (map[temp.blueR][blueNC - 1] == 1) { temp.blueGoal = 1; break; } blueNC--; } if (temp.blueR == temp.redR && redNC == blueNC) { if (temp.redC < temp.blueC) { blueNC++; } else { redNC++; } } if (temp.blueGoal == 0 && temp.redGoal == 1) { cout << temp.cnt + 1; return 0; } if (temp.blueGoal == 0 && temp.redGoal == 0) { temp.cnt++; temp.blueC = blueNC; temp.redC = redNC; q.push(temp); } } // 동 else { node temp = q.front(); int redNC = temp.redC; int blueNC = temp.blueC; while (map[temp.redR][redNC + 1] != -1) { if (map[temp.redR][redNC + 1] == 1) { temp.redGoal = 1; break; } redNC++; } while (map[temp.blueR][blueNC + 1] != -1) { if (map[temp.blueR][blueNC + 1] == 1) { temp.blueGoal = 1; break; } blueNC++; } if (temp.blueR == temp.redR && redNC == blueNC) { if (temp.redC < temp.blueC) { redNC--; } else { blueNC--; } } if (temp.blueGoal == 0 && temp.redGoal == 1) { cout << temp.cnt + 1; return 0; } if (temp.blueGoal == 0 && temp.redGoal == 0) { temp.cnt++; temp.blueC = blueNC; temp.redC = redNC; q.push(temp); } } } // 큐에서 제거 q.pop(); } cout << -1; return 0; }