사다리 타기 문제
- 두 가지 방법을 활용해서 풀어볼 수 있다.
- 2차원 배열에서 델타 배열을 이용해 탐색하는 방법
- 그냥 if 문을 이용해서 조건 비교해서 탐색하는 방법
- 도착 지점을 먼저 찾고 역으로 올라가는 방법과, 첫 행부터 찾아나가는 방법이 있는데 전자가 더 간간단하다.
- 주의해야할 점은 범위가 벗어나서 index error가 나는 것과 지나온 길은 숫자를 바꿔줘서 무한 루프에 빠지지 않게 하는 것이었다.
델타 배열을 이용하는 방법
for _ in range(1, 11):
tc = int(input())
arr = [list(map(int, input().split())) for _ in range(100)]
# 도착지점의 column index 찾기
for c in range(100):
if arr[99][c] == 2:
break
# 도착지점에서 거꾸로 올라가기
r = 99
# 델타 활용, 움직일 수 있는 방향은 세 방향, 세 방향을 돌아가면서 탐색하면서 1이 있는지 확인. 1이 맞다면 그쪽으로 이동
dr = [0,0,-1]
dc = [1,-1,0]
idx = 0
# r가 0행에 도달할 때까지 무한 반복
while r >0:
temp_r = r + dr[idx]
temp_c = c +dc[idx]
if 0 <= temp_r < 100 and 0 <= temp_c <100: # out of index 에러 방지
# 세 가지 방향 중에 1이 있다면 그쪽으로 이동
if arr[temp_r][temp_c] == 1:
r = temp_r
c = temp_c
arr[temp_r][temp_c] = -1 # 1로 그대로 두면 오른쪽으로 이동했다가 1을 보고 다시 왼쪽으로 되돌아와서 무한루프에 빠짐
idx = (idx+1) % 3
print(f'#{tc} {c}')
if 문을 활용하는 방법
for _ in range(1, 11):
tc = int(input())
arr = [list(map(int, input().split())) for _ in range(100)]
# 도착지점의 column index 찾기
for c in range(100):
if arr[99][c] == 2:
break
# 도착지점에서 거꾸로 올라가기
r = 99
## if문 활용하기
while r > 0:
# 왼쪽 먼저 확인
if (c-1 >= 0) and arr[r][c-1] == 1:
arr[r][c] = -1 # 갔다가 다시 되돌아오는 것 방지
c -= 1
# 오른쪽 확인
elif (c+1 < 100) and arr[r][c+1] == 1:
arr[r][c] = -1
c += 1
else:
r -= 1
print(f'#{tc} {c}')