SWEA 1210. [S/W 문제해결 기본] 2일차 - Ladder1 문제 바로가기
문제 접근
우선 도착점에 해당하는 출발지를 찾아야 하기에 도착점부터 시작하여 사다리를 올라가는 방식으로 구현하도록 한다.
처음에는 간단하게 재귀함수로 좌, 우, 상의 순서대로 파악하면서 가면 될 줄 알았다. 하지만 재귀함수의 호출이 너무 많아지기 때문에 재귀함수 제한을 초과하게 된다. 따라서 방향을 추가하여 상,좌,우에 갈림길이 생기지 않는 이상 for문으로 쭉 진행하는 형태로 코드를 구현했다.
문제 풀이
방향이 위일 경우
방향이 위일 경우에 이 함수가 종료된다. 종료될 때의 y값을 출력해야 하기에 리스트에 추가된다. 만약 갈림길이 존재하지 않는다면 위로 쭉 진행되지만 갈림길, 즉, 좌 또는 우측에 1이 있다면 그 갈림길로 이동하고 방향을 좌 또는 우로 지정해준다.
# d=1 => 왼 d=2 => 오른쪽, d=3 => 위
def ladder_up(x,y,d):
if d==3: # 위로쭉
for i in range(x,-1,-1):
if i==0:
result.append(y)
if y-1>=0 and ladder[i][y-1]==1:
d=1 # 방향 왼쪽으로 틀고
ladder_up(i,y-1,d)
break
elif y+1<=99 and ladder[i][y+1]==1:
d=2 # 방향 오른쪽으로 틀고
ladder_up(i,y+1,d)
break방향이 왼쪽일 경우
사다리가 아래로 가지는 않기 때문에 위쪽으로 올라가는 곳만 확인하면 된다. 따라서 왼쪽 방향으로 탐색하다가 위쪽에 1이 발견되면 그 좌표로 이동하고 d를 3으로 바꾸어 위쪽으로 향하게 해준다.
elif d==1: # 왼쪽
for i in range(y,-1,-1):
if ladder[x-1][i]==1:
d=3 # 위
ladder_up(x-1,i,d)
break방향이 오른쪽일 경우
방향이 왼쪽일 때와 반대로 생각하면 된다.
elif d==2: # 오른쪽
for i in range(y,100):
if ladder[x-1][i]==1:
d=3
ladder_up(x-1,i,d)
break시작점 코드
처음 시작은 d=3으로 위로 향하게 한다. 시작점을 도착점인 2를 찾아서 진행한다.
for i, val in enumerate(ladder[99]):
if val == 2:
ladder_up(99,i,3)
break제출 코드
result = []
for _ in range(10):
# 도착 지점에 연결된 출발점을 찾아야 하기 때문에 도착점부터 탐색을 시작한다.
test_case = int(input())
ladder = []
for i in range(100):
line = list(map(int, input().split()))
ladder.append(line)
# d=1 => 왼 d=2 => 오른쪽, d=3 => 위
def ladder_up(x,y,d):
if d==3: # 위로쭉
for i in range(x,-1,-1):
if i==0:
result.append(y)
if y-1>=0 and ladder[i][y-1]==1:
d=1 # 방향 왼쪽으로 틀고
ladder_up(i,y-1,d)
break
elif y+1<=99 and ladder[i][y+1]==1:
d=2 # 방향 오른쪽으로 틀고
ladder_up(i,y+1,d)
break
# 왼쪽으로 쭉
elif d==1:
for i in range(y,-1,-1):
if ladder[x-1][i]==1:
d=3 # 위
ladder_up(x-1,i,d)
break
elif d==2: #
for i in range(y,100):
if ladder[x-1][i]==1:
d=3
ladder_up(x-1,i,d)
break
for i, val in enumerate(ladder[99]):
if val == 2:
ladder_up(99,i,3)
break
print(f'#{test_case} {result[test_case-1]}')
