[Python] 백준, 14503 (구현)

https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

개요

• 사실 해결이 안됨 -- 모티브로 삼은 정답 코드와 어떤 차이가 있는지도 모르겠고, 흐름이나 로직 모두 완벽한듯 한데..
• 앞서 포스팅한 문제처럼 해결 방법이 무궁무진한 "구현" 문항. 
• 처음에 재귀 함수(dfs꼴)로 시도했다가 무수한 실패 끝에 단순 구현만으로 해결 시도

 

해결 방법

 

방향 1 : 재귀 함수 활용

• is_empty 함수 : 상하좌우 방향으로 비어 있는지의 여부 return
• clean 재귀함수 : is_empty가 True일 경우와 False일 경우로 나누어 분기
• 실패 요인 분석 
  1. return 지점이 명확하지 않음 : 재귀가 언제 종료되는지 불확실 (무한 참조)
  2. is_empty 함수의 역할 애매

방향 2 : 단순 반복문

• 방향 관련 배열 수정 : 기존에 활용하던 방식으로
• visited 이중 배열 : 방법 1 에서는 청소한 곳을 2로 표시 - 이건 큰 차이 없어보임

방향 2 : 논리구조

1. is_empty 라는 flag 추가.
   • for 문을 돌면서 True로 바뀌지 않으면 청소할 빈 공간이 없다는 의미
2. 4방향 확인을 위해 for 문 순회
   • d의 순서가 0 -> 3 -> 2 -> 1 의 형식으로 되어야 함 (반시계 방향)
   • 1. 인덱스 안에 포함되며, 2. 해당 공간이 빈 공간이고, 3. 방문한 적이 없을 경우 체크
3. is_empty 가 False 라면
   • 뒤로 후진했을 때 벽이라면 반복문 break
   • 아니라면 x, y 값 갱신

 

★ 2번에서 4방향으로 for 문을 순회하는 이유

• 문제에선 4방향을 모두 (동시에) 확인 후 비었다면 반시계 방향으로 이동이라고 명시
• 이렇게 하는 것보다 반시계 방향 회전 후 한 칸 전진한 곳이 빈 곳(청소가 필요한 곳)이라면 위의 상황과 동치
  • 두번째 문장처럼 하기 위해서 모든 방향에 (기준점에서 반시계씩 네 번 회전하는 건 둘러쌓인 네 곳을 체크하는 것) 빈 곳이 없을 경우 is_empty 플래그 값이 변하지 않으므로 아래 추가 조건에서 거를 수 있음

 

Python Code : 방향 1

import sys

m, n = map(int, sys.stdin.readline().split())
x, y, d = map(int, sys.stdin.readline().split())
room = []

for _ in range(max(n, m)):
    room.append(list(map(int, sys.stdin.readline().split())))


def is_empty(m, n):
    seqs = [[m-1, n], [m, n+1], [m+1, n], [m, n-1]]
    for seq in seqs:
        if (seq[0] < 0) or (seq[1] < 0):
            continue
        else:
            if room[seq[0]][seq[1]] == 0:
                return True
    return False


calcu_seq = [[-1, 0], [0, 1], [1, 0], [0, -1]]
answer = 0


def clean(x, y, d):
    global answer

    if room[x][y] == 0:
        room[x][y] = 2
        answer += 1
    else:
        return

    if is_empty(x, y) == False:
        new_d = int((d + 2) % 4)
        x = x + calcu_seq[new_d][0]
        y = y + calcu_seq[new_d][1]
        if (x < 0) or (y < 0):
            return
        elif room[x][y] == 1:
            return
        else:
            clean(x, y, d)
    else:
        d = int((d + 3) % 4)
        if room[x + calcu_seq[d][0]][y + calcu_seq[d][1]] == 0:
            x = x + calcu_seq[d][0]
            y = y + calcu_seq[d][1]
        clean(x, y, d)


clean(x, y, d)
print(answer)

 

Python Code : 방향 2

import sys

m, n = map(int, sys.stdin.readline().split())
x, y, d = map(int, sys.stdin.readline().split())

room = []
visited = [[0] * n for _ in range(m)]

for _ in range(m):
    room.append(list(map(int, sys.stdin.readline().split())))

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

result = 1

while True:
    is_empty = False
    for _ in range(4):
        d = (d + 3) % 4
        n_dx = x + dx[d]
        n_dy = y + dy[d]
        if (0 <= n_dx < m) and (0 <= n_dy < n) and (room[n_dx][n_dy] == 0):
            if (visited[n_dx][n_dy] == 0):
                visited[n_dx][n_dy] = 1
                x = n_dx
                y = n_dy
                result += 1
                is_empty = True
                break
            # else:
            #     continue

    if not is_empty:
        n_d = (d + 2) % 4
        n_dx = x + dx[n_d]
        n_dy = y + dy[n_d]
        # if (0 <= n_dx < m) and (0 <= n_dy < n):
        if room[n_dx][n_dy] == 1:
            break
        else:
            x = n_dx
            y = n_dy

    # if not is_empty:  # 4방향 모두 청소가 되어 있을 때,
    #     if room[x-dx[d]][x-dy[d]] == 1:  # 후진했는데 벽
    #         print(result)
    #         break
    #     else:
    #         x, y = x-dx[d], y-dy[d]

print(result)