[백준 / BOJ] C++ 12020 LU 분해

12020번: LU 분해

 

문제

https://www.acmicpc.net/problem/12020

12020번: LU 분해

 

 

풀이

선형대수학에서 배우는 LU 분해를 구현하는 문제다. 구현 자체는 LU 분해를 하는 방식대로 하면 된다. LU 분해에 대해선 설명 잘해놓은 다른 블로그를 참고하는 게 좋을 것 같다. 코드에 대한 설명은 아래 코드에 주석으로 설명해 놓았다.

 

문제에서 신경 써야 할 부분은 LU 분해를 할 수 없는 경우에 대한 예외 처리다. 이것 때문에 구글링을 해봤고, LU 분해를 할 수 없는 테스트 케이스를 찾았다.

3
1 0 0
0 0 2
0 -1 1

이 테스트 케이스를 실행해 보니 일부 원소가 nan과 inf으로 출력되었다. nan은 0/0, inf는 양의 무한대, -inf는 음의 무한대였다. 모두 0에 의해 생긴 것이므로 nan에 대한 예외처리를 하면 inf도 해결될 것이라고 생각했다. 구글링을 통해 isnan 함수를 알게 되었고 L, U 행렬 전체에서 nan이 있다면 -1을 출력하고 종료하도록 했다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  vector<vector<double>> L(1001, vector<double>(1001, 0)), U(1001, vector<double>(1001, 0));
  cin >> n;
  // U행렬은 일반행렬을 입력받아 U행렬로 변경
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      cin >> U[i][j];
      // L은 단위행렬
      L[i][j] = i == j ? 1 : 0;
    }
  // LU 분해
  for (int i = 0; i < n - 1; i++) {
    // 대각행렬 원소
    double d = U[i][i];
    // 다음 모든 행
    for (int j = i + 1; j < n; j++) {
      // 첫 번째 원소
      double x = U[j][i] / d;
      // 행의 각 열에 첫 번째 원소가 0이 되도록 뺀다
      for (int k = 0; k < n; k++)
        U[j][k] -= x * U[i][k];
      // L 행렬
      L[j][i] = x;
    }
  }
  // LU 분해를 할 수 없는 경우
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      // L 또는 U에 수가 아닌 것이 있는 경우
      if (isnan(L[i][j]) || isnan(U[i][j])) {
        cout << "-1\n";
        return 0;
      }
  // 소수 4째자리에서 반올림하여 3째자리까지 출력
  cout.precision(3);
  cout << fixed;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++)
      cout << L[i][j] << ' ';
    cout << '\n';
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++)
      cout << U[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}