BOJ 14365 Slides! (Small)

문제 링크:

문제 내용

$B$개의 빌딩에 미끄럼틀을 설치해서, 1번 빌딩에서 $B$번 빌딩으로 갈 수 있도록 하려고 합니다.

미끄럼틀은 임의의 두 빌딩 사이에 설치할 수 있지만, 임의의 $1 \le u, v \le B$에 대해, $u$번 빌딩에서 $v$번 빌딩으로 가는 미끄럼틀은 최대 하나만 설치할 수 있습니다. 또한, 미끄럼틀을 이용하여 한 빌딩에서 다른 빌딩을 통해서 이전 빌딩으로 돌아올 수 있으면 안됩니다.

1번 빌딩에서 $B$번 빌딩으로 가는 서로 다른 방법이 정확히 $M$개가 되도록 미끄럼틀을 설치하는 방법이 있다면, 그러한 방법을 아무거나 하나 출력하세요.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 100$)

각 테스트 케이스에 대해, $B$와 $M$이 한 줄에 주어집니다. ($2 \le B \le 6$, $1 \le M \le 20$)

출력

각 테스트 케이스에 대해, 다음과 같이 출력합니다.

• 미끄럼틀을 설치하는 방법이 있다면, 먼저 한 줄에 Case #{테스트 케이스 번호}: POSSIBLE을 출력하고, 추가로 $B \times B$ 행렬을 출력합니다. 이 행렬의 $i$번째 행의 $j$번째 수는 $i$번 빌딩에서 $j$번 빌딩으로 가는 미끄럼틀이 있으면 1, 아니면 0입니다. 이를 출력할 때는 $B$줄에 걸쳐서 $i$번째 줄에 그 행의 $B$개 값을 공백 없이 출력합니다.
• 미끄럼틀을 설치하는 방법이 없다면, 한 줄에 Case #{테스트 케이스 번호}: IMPOSSIBLE을 출력합니다.

문제 풀이