[Softeer_Python] Lv3. 로봇이 지나간 경로

문제

https://www.softeer.ai/practice/6275

 

 

사용 알고리즘

구현, 시뮬레이션

 

풀이

고려사항

1. 출발점, 출발방향 찾기 - 연결된 곳이 1개인지

2. 다음 방향 설정

 

후기

1.이 문제에서는 출발점 탐색과 경로 이동 두 로직으로 나뉜다.

2. 우선, 출발점은 현재 위치에서 상하좌우를 살피며 이어진 곳이 1곳인지, 2곳인지 확인하여 찾는다.

이어진 곳이 1곳인 경우 출발점으로 시작한다.

이때, 이어진 곳의 방향을 함께 확인하여 출력한다.

3. 이후 경로 이동을 진행하는데 앞으로 전진 시 2칸씩 이동한다.

이때, 2칸씩 이동하더라도 다음 방향 탐색은 1칸을 기준으로 진행해야한다.

#.#과 같이 앞으로 진행은 안되지만 돌아서 2칸 앞에 놓인 곳을 지나가게 되는 경우가 존재하기 때문이다.

처음에는 2칸을 기준으로 갈 수 있는 곳 여부를 확인해서 오답이 나왔다.

1칸을 기준으로 방향 탐색 후 방향이 설정되면 1칸, 2칸 이동 후 모두 visited 처리를 하여 진행하였다.

 

코드

import sys
input = sys.stdin.readline

didj = [(0, 1), (1, 0), (0, -1), (-1, 0)]
didj_emo = ['>', 'v', '<', '^']

def find(ci, cj):
    # 시작점 찾기
    cnt = 0
    for di in range(4):
        ni, nj = ci + didj[di][0], cj + didj[di][1]
        if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] == '#':
            cnt += 1
            start_di = di
            if cnt >= 2:
                return False
    if cnt == 1:
        # 시작점 위치 출력
        print(ci + 1, cj + 1)
        # 방향 출력
        print(didj_emo[start_di])
        # 경로 탐색
        channel(ci, cj, start_di)
        return True

def channel(ci, cj, d):
    answer = ''
    visited = [[0] * M for _ in range(N)]

    while True:
        for i in range(-1, 2):
            nd = (d+i) % 4
            nni, nnj = ci + didj[nd][0], cj + didj[nd][1]
            if 0 <= nni < N and 0 <= nnj < M and arr[nni][nnj] == '#' and visited[nni][nnj] == 0:
                if i == -1:
                    answer += 'LA'
                elif i == 0:
                    answer += 'A'
                else:
                    answer += 'RA'
                d = nd
                ci, cj = ci + 2 * didj[nd][0], cj + 2 * didj[nd][1]
                visited[nni][nnj], visited[ci][cj] = 1, 1
                break
        else:
            print(answer)
            break
                

N, M = map(int, input().split())
arr = [input().rstrip() for _ in range(N)]

for i in range(N):
    for j in range(M):
        if arr[i][j] == '#' and find(i, j):
            sys.exit()

 

결과