[Python/파이썬] 백준 1726번: 로봇

문제

 

풀이

왼쪽 오른쪽 설정

def turnLeft(now):
    if now == 1:    return 4 #동 북
    if now == 2:    return 3 #서 남
    if now == 3:    return 1 #남 동
    if now == 4:    return 2 #북 서

def turnRight(now):
    if now == 1:    return 3 #동 남
    if now == 2:    return 4 #서 북
    if now == 3:    return 2 #남 서
    if now == 4:    return 1 #북 동

 

입력

i, j, dir은 로봇의 위치

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
visited = [[[False] * 5 for _ in range(n)] for _ in range(m)]

i, j, dir = map(int, input().split())
destI, destJ, destDir = map(int, input().split())

 

bfs

1,2,3칸을 움직이던 도중 벽을 만나면 바로 break를 해주었다. (벽은 통과할 수 없음)

def bfs():
    q = deque()
    q.append((i - 1, j - 1, dir, 0))
    visited[i - 1][j - 1][dir] = True
    
    while q:
        si, sj, sdir, cnt = q.popleft()
        if si == destI - 1 and sj == destJ - 1 and sdir == destDir:
            print(cnt)
            return
        
        left, right = turnLeft(sdir), turnRight(sdir)
        
        if not visited[si][sj][left]:
            visited[si][sj][left] = True
            q.append((si, sj, left, cnt + 1))
            
        if not visited[si][sj][right]:
            visited[si][sj][right] = True
            q.append((si, sj, right, cnt + 1))
        
        if sdir in [1, 2]:
            weight = 1
            if sdir == 2:
                weight = -1
            for k in range(1, 4):
                nj = sj + weight * k #1,2,3 만큼 이동
                if nj < 0 or nj >= n or visited[si][nj][sdir]:
                    continue
                if graph[si][nj] == 1:
                    break
                visited[si][nj][sdir] = True
                q.append((si, nj, sdir, cnt + 1))
        
        if sdir in [3, 4]:
            weight = 1
            if sdir == 4:
                weight = -1
            for k in range(1, 4):
                ni = si + weight * k #1,2,3 만큼 이동
                if ni < 0 or ni >= m or visited[ni][sj][sdir]:
                    continue
                if graph[ni][sj] == 1:
                    break
                visited[ni][sj][sdir] = True
                q.append((ni, sj, sdir, cnt + 1))

 

코드

from collections import deque
input = __import__('sys').stdin.readline

def turnLeft(now):
    if now == 1:    return 4 #동 북
    if now == 2:    return 3 #서 남
    if now == 3:    return 1 #남 동
    if now == 4:    return 2 #북 서

def turnRight(now):
    if now == 1:    return 3 #동 남
    if now == 2:    return 4 #서 북
    if now == 3:    return 2 #남 서
    if now == 4:    return 1 #북 동

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]
visited = [[[False] * 5 for _ in range(n)] for _ in range(m)]

i, j, dir = map(int, input().split())
destI, destJ, destDir = map(int, input().split())

def bfs():
    q = deque()
    q.append((i - 1, j - 1, dir, 0))
    visited[i - 1][j - 1][dir] = True
    
    while q:
        si, sj, sdir, cnt = q.popleft()
        if si == destI - 1 and sj == destJ - 1 and sdir == destDir:
            print(cnt)
            return
        
        left, right = turnLeft(sdir), turnRight(sdir)
        
        if not visited[si][sj][left]:
            visited[si][sj][left] = True
            q.append((si, sj, left, cnt + 1))
            
        if not visited[si][sj][right]:
            visited[si][sj][right] = True
            q.append((si, sj, right, cnt + 1))
        
        if sdir in [1, 2]:
            weight = 1
            if sdir == 2:
                weight = -1
            for k in range(1, 4):
                nj = sj + weight * k #1,2,3 만큼 이동
                if nj < 0 or nj >= n or visited[si][nj][sdir]:
                    continue
                if graph[si][nj] == 1:
                    break
                visited[si][nj][sdir] = True
                q.append((si, nj, sdir, cnt + 1))
        
        if sdir in [3, 4]:
            weight = 1
            if sdir == 4:
                weight = -1
            for k in range(1, 4):
                ni = si + weight * k #1,2,3 만큼 이동
                if ni < 0 or ni >= m or visited[ni][sj][sdir]:
                    continue
                if graph[ni][sj] == 1:
                    break
                visited[ni][sj][sdir] = True
                q.append((ni, sj, sdir, cnt + 1))

bfs()

 

마무리

의식의 흐름(?)대로 문제에서 주어진 것을 구현하니 맞았다.