(JAVA) 백준 2224번 : 명제 증명 --- [플로이드 - 와샬]

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

2224번: 명제 증명

 

안녕하세요.

 

플로이드 - 와샬 문제입니다.

 

 

이 문제와 비슷하게 해결하면 될 것 같습니다.

https://maivve.tistory.com/228

(JAVA) 백준 1613번 : 역사 --- [벨만포드]

 

위 문제와 한 가지 다른 점은

 

2차원 boolean 배열의 index 기준입니다.

 

 

여기서는 A-Z , a-z 문자를 index 0 ~ 51(대문자 26개, 소문자 26개) 로 바꿔서 저장했다는 점입니다.

 

 

아, 그리고 또 하나!

이 부분! 을 if조건에 포함하여 y,x 인덱스가 같지 않은 경우에 출력하는 걸로! 코딩해야합니다.

 

 

이렇게 인덱스로 저장하고 출력을 위해 다시 탐색할 때

굳이 알파벳 순으로 오름차순 정렬을 할 필요가 없다는 장점이 있습니다 ㅎㅎ

 

 

 

매커니즘

---

  1)  boolean 2차원 배열 생성(size : 26 + 26 = 52)

 

  2)  n개만큼 입력받기 시작

 

  3)  입력 받은 두 문자 아스키코드를 활용하여 index 순서로 변경

    *** int x(또는 y) = chA <= 90 ? chA - 'A' : chA - 'a' + 26; // 90은 'A' 의 아스키코드. 26을 더한 이유는 대문자 26개 다음에 소문자가 오기 때문입니다.

 

  4)  3) 에 맞게 boolean 2차원 배열 [y][x] 의 값 true로 변경

 

  5)  벨만 포드 알고리즘을 활용해 a->b, b->c 이면 a->c 를 만족하는 모든 경우의 수 찾아서 해당 배열 값 true로 변경

 

  6)  2중 for문으로 true일 경우, index -> 문자 로 변경 후 StringBuilder 저장

 

  7)  결과 출력!

 

 

 

이상입니다.

 

더 궁금하신 사항은 하단 소스코드 참고바랍니다. 댓글도 부탁드려요!

 

 

감사합니다!

 

 

소스코드

---