SWEA 1210 사다리

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh 

SW Expert Academy

코드를 구현하기 전에 해야하는 생각

이 말은 내가 도달해야하는 지점 (X표시 지점)이 고정되어있다는 것을 의미한다.

지금은 시작점:?

            끝점: X표시

이니까

고정된 끝점에서 사다리를 따라가면 마지막에 내가 원하는 시작점에 도달할 수 있겠다고 생각하면 된다.

 

 

따라서 맨 끝점에 있는 x좌표를 먼저 찾아주기로 했다

T = 10
for tc in range(1, T+1):
    n = int(input())
    ladder = [list(map(int, input().split())) for _ in range(100)]

    # 시작점 찾기 (맨끝줄의 x좌표 찾기)
    x = 0
    for s in range(100):
        if ladder[99][s] == 2:
            x= s
    y = 99

시작점은 2라고 했으니까 찾아준 후, 시작점 x, y를 따로 변수에 저장했다.

    # 다이렉트배열 (오른쪽이나 왼쪽에 갈수있는 길 있으면 오,왼 먼저인거 확인)
    dy = [0, 0, -1]
    dx = [-1, 1, 0]

사다리 탈때, 위로 올라가면서

양옆에 갈 수 있는 길이 생기면 무조건 그쪽으로 가야된다!!

그래서 다이렉트 배열을 만들때 x쪽을 먼저가게끔 만들어줘야한다

 

    while y>=0:
        for i in range(3):
            # 다음에 가는 칸 확인
            ny = y+dy[i]
            nx = x+dx[i]
            #범위 벗어나면 다음거로 넘어가기
            if nx<0 or nx>99 or ny>99:
                continue

            if ladder[ny][nx] == 1:
                idx = i
                ladder[y][x] = 3 #이미 갔던 칸 안가도록 체크 해주기
                y+=dy[idx]
                x+=dx[idx]
                break

    print(f'#{tc} {x}')

for문을 돌면서 다음에 내가 갈 칸을 확인하고, 조건이 맞으면 다음칸으로 간다.

1이라는 숫자가 사다리를 표시하니까 좌표값이 1이면, 그쪽으로 간다고 코드를 짜준다.

이때, 내가 이미 지나간 칸은 1이 아닌 다른 문자나 숫자로 꼭 표시를 해줘야한다!!!

이걸 안하면 사다리의 한 칸에서 좌우로만 무한루프를 돌게된다는 것을 알게됨...(나도 알고싶지 않았다)

 

 

1) 사다리에서 끝점을 알고있으면, 시작~끝으로 가지 말고 끝~시작으로 간다고 생각하기

2) 사다리는 양옆으로 길이 있으면 무조건 그쪽으로 가니까 다이렉트 배열짤때 주의하기

3) 이미 갔던 칸을 돌아가는 일이 없도록 숫자 바꿔주기

만 주의하면 되는 문제였다

 

 

 

전체코드는 이러하다.

T = 10
for tc in range(1, T+1):
    n = int(input())
    ladder = [list(map(int, input().split())) for _ in range(100)]
    
    # 시작점 찾기 (맨끝줄의 x좌표 찾기)
    x = 0
    for s in range(100):
        if ladder[99][s] == 2:
            x= s
    y = 99

    # 다이렉트배열 (오른쪽이나 왼쪽에 갈수있는 길 있으면 오,왼 먼저인거 확인)
    dy = [0, 0, -1]
    dx = [-1, 1, 0]
    
    
    while y>=0:
        for i in range(3):
            # 다음에 가는 칸 확인
            ny = y+dy[i]
            nx = x+dx[i]
            #범위 벗어나면 다음거로 넘어가기
            if nx<0 or nx>99 or ny>99:
                continue
            
            if ladder[ny][nx] == 1:
                idx = i
                ladder[y][x] = 3 #이미 갔던 칸 안가도록 체크 해주기
                y+=dy[idx]
                x+=dx[idx]
                break

    print(f'#{tc} {x}')