문제
점심 시간에 산책을 다니는 사원들은 최근 날씨가 더워져, 사다리 게임을 통하여 누가 아이스크림을 구입할지 결정하기로 한다.
김 대리는 사다리타기에 참여하지 않는 대신 사다리를 그리기로 하였다.
사다리를 다 그리고 보니 김 대리는 어느 사다리를 고르면 X표시에 도착하게 되는지 궁금해졌다. 이를 구해보자.
아래 <그림 1>의 예를 살펴보면, 출발점 x=0 및 x=9인 세로 방향의 두 막대 사이에 임의의 개수의 막대들이 랜덤 간격으로 추가되고(이 예에서는 2개가 추가됨) 이 막대들 사이에 가로 방향의 선들이 또한 랜덤하게 연결된다.
X=0인 출발점에서 출발하는 사례에 대해서 화살표로 표시한 바와 같이, 아래 방향으로 진행하면서 좌우 방향으로 이동 가능한 통로가 나타나면 방향 전환을 하게 된다.
방향 전환 이후엔 다시 아래 방향으로만 이동하게 되며, 바닥에 도착하면 멈추게 된다.
문제의 X표시에 도착하려면 X=4인 출발점에서 출발해야 하므로 답은 4가 된다. 해당 경로는 별도로 표시하였다.
아래 <그림 2>와 같은 100 x 100 크기의 2차원 배열로 주어진 사다리에 대해서, 지정된 도착점에 대응되는 출발점 X를 반환하는 코드를 작성하라 (‘0’으로 채워진 평면상에 사다리는 연속된 ‘1’로 표현된다. 도착 지점은 '2'로 표현된다).
[제약 사항]
한 막대에서 출발한 가로선이 다른 막대를 가로질러서 연속하여 이어지는 경우는 없다.
[입력]
입력 파일의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.
총 10개의 테스트 케이스가 주어진다.
[출력]
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 도착하게 되는 출발점의 x좌표를 출력한다.
풀이
처음에 출발점을 모든 사다리로 하려고했으나, 시간초과가 나와서 거꾸로 배열의 값이 2인 사다리를 출발점으로 잡고 이동후 최종 도착점의 column 값을 출력하는 방향으로 진행했다.
그리고 현재위치에서 위로갈지 좌우로 갈지 선택해야 하는데, 현재위치가 양쪽끝인 경우와 아닌 경우로 나누어서 진행하였다.
그리고 왼쪽으로 이동해야 하는 경우는 현재위치에서 col값을 1 감소 시키고 왼쪽으로 이동시킬 수 있는 만큼 이동시키다가, 위쪽으로 이동할 수 있는 경우(현재위치의 위쪽값이 1 인경우)에 while문을 빠져나오고, row값을 1감소 시켜 위로 이동한다.
오른쪽의 경우도 마찬가지로 진행한다.
코드
for _ in range(10):
test_case = int(input())
ladder=[]
first_column=0
for _ in range(100):
ladder.append(list(map(int, input().split())))
#첫 시작 컬럼찾기
for i in range(100):
if ladder[99][i] == 2:
first_column = i
row = 99
col = first_column
while row > 0:
if col == 0: #현재 위치가 왼쪽 젤 끝인 경우
if ladder[row][col + 1] == 1 and ladder[row - 1][col] == 1: # 오른쪽으로 이동
col += 1
while ladder[row - 1][col] == 0:
col += 1
row -= 1
elif ladder[row][col + 1] == 0 and ladder[row - 1][col] == 1: #위쪽 이동
row -= 1
elif col == 99: #현재 위치가 오른쪽 젤 끝인 경우
if ladder[row][col - 1] == 1 and ladder[row - 1][col] == 1: # 왼쪽으로 이동
col -= 1
while ladder[row-1][col] == 0:
col -= 1
row -= 1
elif ladder[row][col - 1] == 0 and ladder[row - 1][col] == 1: #위쪽 이동
row -= 1
else: # 현재 위치가 양쪽 끝이 아닌 경우(사이인 경우)
if ladder[row][col+1] == 1: #오른쪽 이동
col += 1
while ladder[row-1][col] == 0:
col += 1
row -= 1
elif ladder[row][col-1] == 1: #왼쪽 이동
col -= 1
while ladder[row-1][col] == 0:
col -= 1
row -= 1
else:
row -= 1
print(f'#{test_case} {col}')
