백준 14503 로봇청소기 파이썬 풀이, 반례

난이도 : 골드5
풀이일 : 04204
https://www.acmicpc.net/problem/14503

14503번: 로봇 청소기

---

링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐

---

1차 시도 오답 -> 1% 틀렸습니다.

import sys

def clean(arr, i, j, h):
    sell = 0
    while True:
        if arr[i][j] == 0:
            arr[i][j] = -1
            sell += 1
        next_sell = 0
        for k in range(4):
            ni = i + hi[k]
            nj = j + hj[k]
            if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] == 0:
                next_sell += 1
        if next_sell:
            h -= 1
            if 0 <= i + hi[h % 4] < N and 0 <= j + hj[h % 4] < M:
                if arr[i + hi[h % 4]][j + hj[h % 4]] == 0:
                    i = i + hi[h % 4]
                    j = j + hj[h % 4]
        else:
            if 0 <= i + hi[(h + 2) % 4] < N and 0 <= j + hj[(h + 2) % 4] < M:
                i = i + hi[(h + 2) % 4]
                j = j + hj[(h + 2) % 4]
            else:
                return print(sell)


N, M = map(int, sys.stdin.readline().split())
r, c, h = map(int, sys.stdin.readline().split())
room = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

hi = [-1, 0, 1, 0]
hj = [0, 1, 0, -1]

clean(room, r, c, h)

코드 구성
1. 문제에서 주어진 조건이 구체적이라서 그대로 코드 구현
2. 현재 칸이 청소되지 않은 경우, 청소하고 sell + 1
3. 청소한 현재 칸은 벽, 미청소칸과 구분을 위해 -1 할당
4. 현재 칸 주변 4칸 중 청소되지 않은 칸이 있는지 조사
5. 청소되지 않은 칸이 있다면, 반시계 방향 90도 회전 후 바라보는 방향이 미청소칸일 시 전진
6. 방향 설정은 입력에서 주어지는 순서대로 하고, 회전 방향을 -1로 설정
7. 청소되지 않은 칸이 있다면, 바라보는 방향 유지, 한 칸 후진
 
틀린 이유
1. 네 면이 벽인 경우에도 계속 이동하며 벽으로 가로막힌 지역도 청소

---

2차 시도 오답 -> 1% 틀렸습니다.

import sys

def clean(arr, i, j, h):
    sell = 0
    while True:
        if arr[i][j] == 0:
            arr[i][j] = -1
            sell += 1
        next_sell = 0
        wall = 0
        for k in range(4):
            ni = i + hi[k]
            nj = j + hj[k]
            if 0 <= ni < N and 0 <= nj < M:
                if arr[ni][nj] == 0:
                    next_sell += 1
                elif arr[ni][nj] == 1:
                    wall += 1
        if wall == 4:
            return print(sell)
        if next_sell:
            h -= 1
            if 0 <= i + hi[h % 4] < N and 0 <= j + hj[h % 4] < M:
                if arr[i + hi[h % 4]][j + hj[h % 4]] == 0:
                    i = i + hi[h % 4]
                    j = j + hj[h % 4]
        else:
            if 0 <= i + hi[(h + 2) % 4] < N and 0 <= j + hj[(h + 2) % 4] < M:
                i = i + hi[(h + 2) % 4]
                j = j + hj[(h + 2) % 4]
            else:
                return print(sell)


N, M = map(int, sys.stdin.readline().split())
r, c, h = map(int, sys.stdin.readline().split())
room = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

hi = [-1, 0, 1, 0]
hj = [0, 1, 0, -1]

clean(room, r, c, h)

코드 변화
1. 네 면이 모두 벽인 경우 sell 출력 반환하도록 wall 변수, 관련 코드 추가
 
틀린 이유
1. 후진 할 곳이 벽인 경우에도 후진

---

최종 정답

# 1. 현재 칸이 청소되지 않은 경우, 현재 칸 청소
# 2. 현재 칸 주변 4칸 중 청소되지 않은 빈 칸 없는 경우
#    바라보는 방향 유지, 한 칸 후진이 가능하다면 한 칸 후진 후 1로 돌아감
#    한 칸 후진이 불가능하다면 작동 중지
# 3. 현재 칸 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우
#    반시계 방향으로 90도 회전
#    바라보는 방향 기준 앞쪽 칸이 청소되지 않은 빈칸이라면 한 칸 전진 후 1로 돌아감

# 1차 시도 1% 틀렸습니다. -> 벽일때도 후진해서 문제 발생

import sys
sys.stdin = open('input.txt')

def clean(arr, i, j, h):
    sell = 0
    while True:
        if arr[i][j] == 0:
            arr[i][j] = -1    # 벽, 미청소칸과 구분
            sell += 1
        next_sell = 0
        wall = 0
        for k in range(4):
            ni = i + hi[k]
            nj = j + hj[k]
            if 0 <= ni < N and 0 <= nj < M:
                if arr[ni][nj] == 0:
                    next_sell += 1
                elif arr[ni][nj] == 1:
                    wall += 1
        if wall == 4:    # 사방이 벽으로 막혀있다면 중단
            return print(sell)
        if next_sell:
            h -= 1    # 반시계 방향 90도 회전
            ni, nj = i + hi[h % 4], j + hj[h % 4]
            # 방향 회전 후 앞 칸이 미청소 칸이면 한 칸 전진
            if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] == 0:
                i, j = ni, nj
        else:
            # 후진을 위해 h+2 활용, 단, h 값은 변함 없음
            ni, nj = i + hi[(h + 2) % 4], j + hj[(h + 2) % 4]
            if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] != 1:
                i, j = ni, nj
            else:    # 후진이 불가능하면 청소칸 출력반환
                return print(sell)


N, M = map(int, sys.stdin.readline().split())
r, c, h = map(int, sys.stdin.readline().split())
room = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

hi = [-1, 0, 1, 0]    # 북 동 남 서
hj = [0, 1, 0, -1]

clean(room, r, c, h)

코드 변화
1. 가독성 개선을 위해 ni, nj 정의 후 조건 확인
2. 주변 4방향 중 미청소 칸이 없을 때, 후진 시 뒷 면이 벽인지 확인하는 코드 추가

---

반례

입력	4 4 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1	5 5 1 2 3 1 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 1 1 1 1 1 1	6 7 2 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1	9 7 3 4 2 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
출력	1	8	15	17

---

느낀점
문제에서 조건을 상세하게 줘도 두 번이나 틀린데에서 반성해야 한다.
꼼꼼히 문제를 읽고 제출하기 전에 틀린 부분은 없는지 상세히 살펴보자