240325 [BOJ/백준] 14503. 로봇 청소기

 

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

14503번: 로봇 청소기

 

---

코드

1. 성공

# 로봇청소기

from collections import deque

N, M = map(int, input().split())
si, sj, direction = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]

di = [-1, 0, 1, 0]  # 상,우,하,좌 방향설정
dj = [0, 1, 0, -1]

q = deque()
q.append([si, sj, direction])
arr[si][sj] = 2  # 벽 1과 구분하기 위해 청소한 곳은 2로 설정
visited[si][sj] = 2
count = 1
while q:
    i, j, dir = q.popleft()
    for k in range(4):  # 반시계방향으로 둘러보며 청소되지 않은 빈 칸 청소하기
        new_dir = (dir - k + 3) % 4
        ni = i + di[new_dir]
        nj = j + dj[new_dir]

        if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] == 0 and visited[ni][nj] == 0:
            visited[ni][nj] = 2  # 청소한다.
            arr[ni][nj] = 2
            count += 1
            q.append([ni, nj, new_dir])
            break

    else:  # 반시계방향으로 둘러보며 청소되지 않은 빈칸이 없다면
        ni = i - di[dir]
        nj = j - dj[dir]
        if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] != 1:
            if not visited[ni][nj]:  # 방문을 안한 곳이면
                visited[ni][nj] = 2  # 청소한다.
                arr[ni][nj] = 2
                count += 1
            q.append([ni, nj, dir])  # 방문(청소)를 했든 안했든 그 위치로 간다.


print(count)

 

2. 교수님 코드 (보자마자 감탄사 나온 진짜 간단한 코드... 멋있어요!)

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

N, M = map(int, input().split())
x, y, d = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(N)]

#0 북쪽, 1 동쪽, 2 남쪽, 3 서쪽
ans = 0
while True:

    if MAP[x][y] == 0:
        MAP[x][y], ans = 2, ans + 1

    for i in range(1, 5):
        ld = (d - i) % 4
        lx, ly = x + dx[ld], y + dy[ld]
        if MAP[lx][ly] == 0:
            x, y, d = lx, ly, ld
            break
    else:
        bd = (d + 2) % 4
        bx, by = x + dx[bd], y + dy[bd]
        if MAP[bx][by] == 1:
            break
        else:
            x, y = bx, by

print(ans)

 

내가 제일 처음 짰던 코드(결과 안나옴)

from collections import deque

N, M = map(int,input().split())
si, sj, direction = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
visited = [[0]*M for _ in range(N)]
# print(arr)
di = [0, 1, 0, -1]  # 좌,하,우,상 방향설정(반시계 90도)
dj = [-1, 0, 1, 0]

q = deque()
q.append([si, sj])
arr[si][sj] = 2  # 벽 1과 구분하기 위해 청소한 곳은 2로 설정
visited[si][sj] = 2
count = 1
while q:
    i, j = q.popleft()
    # print(i)
    # print(j)
    for k in range(4):  # 반시계방향으로 둘러보며 청소되지 않은 빈 칸 청소하기
        ni = i + di[k]
        nj = j + dj[k]

        if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] == 0 and visited[ni][nj] == 0:
            visited[ni][nj] = 2  # 청소한다.
            arr[ni][nj] = 2
            count += 1
            q.append([ni, nj])
            break

    else:  # 반시계방향으로 둘러보며 청소되지 않은 빈칸이 없다면
        if direction % 2 == 0:  # 바라보는 방향이 북, 남 일 경우
            z = direction + 1   # 후진 방향 인덱스 값 구함
        else:
            z = direction - 1

        ni = i + di[z]
        nj = j + dj[z]
        if 0 <= ni < N and 0 <= nj < M and arr[ni][nj] != 1:
            q.append([ni, nj])

print(count)

결과

---

문제에 나와있는 것처럼 큐로 arr를 돌며 청소하는 것들을 완벽하게 코드로 구현했다고 생각했다. 안된 이유는 일단 di, dj를 반시계방향으로 설정했어도 현재의 방향에 따라 di, dj가 적용되는게 달라질 수 있다는 진우의 얘기를 듣고 한번 코드를 고쳤다. 그 이후에 방향을 저장하지 않고 방향설정도 조금은 어렵게 해서 답이 나오지 않았다. 교수님과 현조의 도움으로 나의 로봇청소기가 청소한 구역의 갯수를 구할 수 있었다!