Development/Algorithm

[백준 / Python] 14503 - 로봇 청소기

안다희 2020. 11. 25. 02:01
728x90

결과

  • 메모리 123264 KB
  • 시간 116 ms

알게된 것

  • bfs에서 도중에 return 하는 예시도 연습해봤다.

푼 과정

  • directions 순서가 방향마다 달라서 getDirections를 만들었다.
  • bfs 처음에 매번 print(a, b) 해서 내가 의도한대로 동작하는지 다 따라가봤다. 역시 직접 해보는게 제일 빠르다!

제출 코드

# 제출
N, M = map(int, input().split())
robotR, robotC, currentD = map(int, input().split())
area = [list( map(int, input().split()) ) for _ in range(N)]

directions = [(0, -1), (1, 0), (0, 1), (-1, 0)] # 북 기준

def getDirectios(d):
    if d == 0:
        return [(0, -1, 3), (1, 0, 2), (0, 1, 1), (-1, 0, 0)]
    if d == 1:
        return [(-1, 0, 0), (0, -1, 3), (1, 0, 2), (0, 1, 1)]
    if d == 2:
        return [(0, 1, 1), (-1, 0, 0), (0, -1, 3), (1, 0, 2)]
    if d == 3:
        return [(1, 0, 2), (0, 1, 1), (-1, 0, 0), (0, -1, 3)]

def getXYToBack(a, b, d):
    if d == 0:
        return (a + 1, b)
    if d == 1:
        return (a, b - 1)
    if d == 2:
        return (a - 1, b)
    if d == 3:
        return (a, b + 1)

def bfs(a, b, _currentD):
    area[a][b] = 2
    for x, y, d in getDirectios(_currentD):
        dx, dy = x + a, y + b
        if 0 <= dx < N and 0 <= dy < M and area[dx][dy] == 0:
            bfs(dx, dy, d)
            return
    # 여기까지 왔다는건, 네 방향 모두 다 못갔다는 것
    dx, dy = getXYToBack(a, b, _currentD) # 후진할 x, y 구하기
    if 0 <= dx < N and 0 <= dy < M and not area[dx][dy] == 1:
        bfs(dx, dy, _currentD)

def getCleanedCount():
    count = 0
    for i in range(N):
        for j in range(M):
            if area[i][j] == 2:
                count += 1
    return count

bfs(robotR, robotC, currentD)
count = getCleanedCount()
print(count)

테스트용 코드

# N, M = map(int, input().split())
# robotR, robotC, currentD = map(int, input().split())
# area = [list( map(int, input().split()) ) for _ in range(N)]

# N, M = 3, 3
# robotR, robotC, currentD = 1, 1, 0
# area = [
#     [1, 1, 1],
#     [1, 0, 1],
#     [1, 1, 1]
# ]

# N, M = 11, 10
# robotR, robotC, currentD = 7, 4, 0
# area = [
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
#     [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
#     [1, 0, 0, 0, 1, 1, 1, 1, 0, 1],
#     [1, 0, 0, 1, 1, 0, 0, 0, 0, 1],
#     [1, 0, 1, 1, 0, 0, 0, 0, 0, 1],
#     [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
#     [1, 0, 0, 0, 0, 0, 0, 1, 0, 1],
#     [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
#     [1, 0, 0, 0, 0, 0, 1, 1, 0, 1],
#     [1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
#     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
# ]

N, M = 3, 5
robotR, robotC, currentD = 1, 2, 1
area = [
    [1, 1, 1, 1, 1],
    [1, 0, 0, 0, 1],
    [1, 1, 1, 1, 1]
]

directions = [(0, -1), (1, 0), (0, 1), (-1, 0)] # 북 기준

def getDirectios(d):
    if d == 0:
        return [(0, -1, 3), (1, 0, 2), (0, 1, 1), (-1, 0, 0)]
    if d == 1:
        return [(-1, 0, 0), (0, -1, 3), (1, 0, 2), (0, 1, 1)]
    if d == 2:
        return [(0, 1, 1), (-1, 0, 0), (0, -1, 3), (1, 0, 2)]
    if d == 3:
        return [(1, 0, 2), (0, 1, 1), (-1, 0, 0), (0, -1, 3)]

def getXYToBack(a, b, d):
    if d == 0:
        return (a + 1, b)
    if d == 1:
        return (a, b - 1)
    if d == 2:
        return (a - 1, b)
    if d == 3:
        return (a, b + 1)

def bfs(a, b, _currentD):
    print(a, b)
    area[a][b] = 2
    for x, y, d in getDirectios(_currentD):
        dx, dy = x + a, y + b
        if 0 <= dx < N and 0 <= dy < M and area[dx][dy] == 0:
            bfs(dx, dy, d)
            return
    # 여기까지 왔다는건, 네 방향 모두 다 못갔다는 것
    dx, dy = getXYToBack(a, b, _currentD) # 후진할 x, y 구하기
    print('a b dx dy', a, b, dx, dy)
    if 0 <= dx < N and 0 <= dy < M and not area[dx][dy] == 1:
        bfs(dx, dy, _currentD)

def getCleanedCount():
    count = 0
    for i in range(N):
        for j in range(M):
            if area[i][j] == 2:
                count += 1
    return count

def printArr(arr):
    for a in arr:
        print(a)

bfs(robotR, robotC, currentD)
print('----')
count = getCleanedCount()
printArr(area)
print(count)
출처: https://mingos-habitat.tistory.com/34 [밍고의서식지:티스토리]