퀴즈

*채용퀴즈풀이를 함께 제출하셔야 접수가 됩니다.

문제

NxN 크기의 격자 모양 방들이 존재하고, 각 방안에는 1~9 사이의 숫자들이 있습니다. 
임의의 방에서 시작하여 인접한 방들로 이동할 수 있으며 이동시에는 해당 방에 쓰여있는 숫자들을 더하면서 이동하게 됩니다. 

단, 다음 방으로 이동할때에는왼쪽 또는 위쪽으로는 이동할 수 없고,
오른쪽 또는 아래쪽으로 인접한 방으로만 이동 가능하며 방향 전환은 한번만 가능합니다.
특정한 숫자 S가 주어질때 임의의 방에서 시작하여 이동할 때 이동 경로의 숫자 총합이 S가 되는 모든 경우를 찾아서 
한 행에 하나의 경로씩 출력해주세요. 각 경로들 사이에서의 순서는 상관없지만 하나의 경로 안에서 숫자들의 순서는 이동 경로 그대로 출력되어야 합니다

구현에 사용할 입력은 아래에 설명된 “num_rooms.txt”와 같은 구조로 제공됩니다.
입력을 반드시 파일로 처리할 필요는 없으며 코드 안에 변수(문자열 혹은 배열 등)로 선언하여 사용하는 것도 가능합니다. 

 <num_rooms.txt 파일의 구조>
 1번 라인: N의 값
 2번 라인: S의 값
 3번 라인 부터 각 방에 포함된 숫자 목록, 열은 공백으로 구분하며 행은 개행으로 구분

입력 예)

num_rooms.txt

출력 예)

<4 2 4 1>

<6 2 1 2>

<2 4 5>

틀린 방향 탐색
빨간색 화살표 방향은 좌측 탐색 방향이 되므로 조건에 맞지 않음

*<6 2 2 1> 경로로 이동하여도 숫자들의 합이 11이 되지만 
방들을 이동할 때 오른쪽 또는 아래쪽으로만 이동가능하기 때문에 이러한 경우는 유효하지 않습니다.