오늘의 회고

14503번 로봇 청소기 문제를 풀었다. 이건 특정 알고리즘이 아니라 그냥 구현 문제인데 아이디어를 어떻게 떠올리냐가 관건이다.

풀이

문제 풀면서 예외처리를 엄청나게 하다가 정말 효율적인 방법이 없을까하고 풀이를 찾아봤다. 찾아보면서 알게 된 사실이 여러가지 있다.

반시계 방향으로 90도 회전

북동남서 0123을 반시계방향으로 회전하면 3012가 된다.
이걸 한 번에 나타내는 식은 다음과 같다.

(d+3) % 4

( 좀 충격이었다. 난 이걸 d에서 1을 빼고 d가 음수면 3으로 지정하는 식으로 풀고 있었다. 이렇게 간단한 방법이 있었다니.)

후진

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
현재 위치에서 방향을 빼주면 그게 후진이 된다.

어떻게 이런 생각을 하지?

room[r][c]에서의 후진값은
room[r-dr[d]][c-dc[d]]

이 문제의 로직을 정리하면 다음과 같다.
1. 반시계 방향으로 90도 회전하고 청소가 가능하면 방문 처리, 청소, 위치 갱신
(청소가 가능하다 = 동서남북 중 빈칸이 있다.)
2. 동서남북 빈칸이 없으면?

• 후진해서 벽이면 break
• 아니면 위치 갱신

+) 동서남북에 빈칸 여부를 확인하는 방법은 flag 변수를 이용해 False로 초기화했다가 만약 빈칸이 하나라도 있어 청소를 해줬다면 True로 바꿔주면 된다. 즉, flag False => 동서남북 빈칸X, True => 동서남북 빈칸O

코드

#14503 로봇 청소기

n, m = map(int, input().split())
r, c, d = map(int, input().split())
# 북동남서 0123
room = [list(map(int, input().split())) for _ in range(n)]
# 방문
visited = [[0]*m  for _ in range(n)]

# 시작 지점
cnt = 1
visited[r][c] = 1

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

while True:
    flag = False # 아직 청소X
    for _ in range(4): # 동서남북 돌기
        d = (d+3) % 4 # 왼쪽 방향으로 돌리기
        nr = r + dr[d]
        nc = c + dc[d]

        # 범위 안 and 빈칸 => 청소 가능
        # 방문해서 청소, cnt, 위치 갱신, flag 변경
        if 0 <= nr < n and 0 <= nc < m and room[nr][nc] == 0:
            if visited[nr][nc] == 0:
                visited[nr][nc] = 1
                cnt += 1
                r, c = nr, nc
                flag = True #청소했다는 뜻
                break
    if not(flag): # flag false 즉, 위 for문에 안들어감
        # 네 방향 모두 청소X
        # 후진시 벽이면 break
        # 벽이 아니면 갱신
        if room[r-dr[d]][c-dc[d]] == 1: # 벽이라면 +) 내가 가지고 있는 방향을 빼주면 후진값
            print(cnt)
            break
        else:
            r,c = r-dr[d], c-dc[d]