[Softeer][level3] 로봇이 지나간 경로 (python)

https://softeer.ai/practice/info.do?idx=1&eid=577 

Softeer

 

문제

 

풀이

bfs로 풀이.

처음 시작점을 찾을 때, '#'인 경우를 찾고 주변에 '#'이 유일한 경우(이동할 수 있는 곳이 정해진 경우) 시작점으로 판단.

마지막에 경로 추가할 때, 이 전에 같은게 나왔는지 여부에 따라 flag로 구별하여 R, L이 추가될 수 있도록 설정.

 

코드

import sys
from pprint import pprint
from collections import deque

H, W = map(int, input().split())
map = [list(sys.stdin.readline().rstrip()) for h in range(H)]

visited = [[0] * W for _ in range(H)]
directions = ['>', '^', '<', 'v']       # 동,북,서,남
ans = []

dc = [1, 0, -1, 0]  # directions와 순서 맞춰서
dr = [0, -1, 0, 1]

def isStart(r, c) :             # 시작 지점과 시작 방향 찾기
    cnt = 0
    for i in range(4) : 
        nx = r + dr[i]
        ny = c + dc[i]
        if 0 <= nx < H and 0 <= ny < W :
            if map[nx][ny] == '#' :     # 주변 4방향 중 '#'이 있는 경우
                cnt += 1
                start_direction = directions[i]
    
    if cnt == 1 :   # 주변에 '#'인 곳이 유일한 경우 시작점으로
        return 1
    else :
        return 0

def BFS(r, c) :
    path = []       # 경로 저장용
    queue = deque()
    queue.append([r,c])
    visited[r][c] = 1

    while queue :
        row, col = queue.popleft()
        for i in range(4) :
            nr = row + dr[i]
            nc = col + dc[i]
            direction = directions[i]

            if 0 <= nr < H and 0 <= nc < W :
                if map[nr][nc] == '#' and not visited[nr][nc] :
                    visited[nr][nc] = 1
                    queue.append([nr, nc])
                    path.append(direction)
    
    return path

for h in range(H) :
    for w in range(W) :
        if map[h][w] == '#' and isStart(h, w) :     # 시작점인 경우
            print(h + 1, w + 1)
            path = BFS(h, w)
            print(path[0])
            
            tmp = 0
            flag = 0        # 이 전에 연속되었는지 판단하는 flag
            for p in range(len(path) - 1) :      # 명령어 출력
                if flag :
                    flag = 0
                    if path[p] == path[p + 1] :
                        continue
                    else :
                        if directions[(directions.index(path[p]) + 1) % 4] == path[p + 1] :   # L인 경우
                            ans.append('L')
                        else :      # R인 경우
                            ans.append('R')
                if path[p] == path[p + 1] :
                    ans.append('A')
                    flag = 1
            
            for i in ans :
                print(i, end='')
            sys.exit(0)