14503. 로봇 청소기

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

# output: 청소하는 영역의 개수
# N * M
# 동서남북
# 반시계 방향으로 90도 회전

# dfs
def dfs(x, y, d):
    global count
    # 방향 : 북 / 동 / 남 / 서
    # direction = [0, 1, 2, 3]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    if not visited[x][y]:
        visited[x][y] = 1
        # 아직 청소되지 않은 경우, 현재 칸을 청소한다.
        if graph[x][y] == 0:
            graph[x][y] = 1
            count += 1

    aldy_cln = 0
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if graph[nx][ny] == 1:
            aldy_cln += 1

    # 청소되지 않은 빈 칸이 없는 경우
    if aldy_cln == 4:
        # 방향은 유지하되, 후진 가능하면 후진
        j = (d + 2) % 4
        nx, ny = x + dx[j], y + dy[j]
        if (0 <= nx < n) and (0 <= ny < m):
            dfs(nx, ny, d)
        # 후진 할 수 없으면 멈춤
        else:
            return

    # 청소되지 않은 빈 칸이 있는 경우
    else:
        # 반시계 방향으로 90도 회전
        d = (d + 3) % 4
        nx, ny = x + dx[d], y + dy[d]
        # 청소 및 방문 처리

        if (0 <= nx < n) and (0 <= ny < m) and not graph[nx][ny]:
            visited[nx][ny] = 1
            graph[nx][ny] = 1
            count += 1
            dfs(nx, ny, d)

        dfs(x, y, d)



# main
n, m = map(int, input().split())

start_x, start_y, d = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]


count = 0

dfs(start_x, start_y, d)

print(count)

# output: 청소하는 영역의 개수
# N * M
# 동서남북
# 반시계 방향으로 90도 회전

# dfs
def dfs(x, y, d):
    global count
    # 방향 : 북 / 동 / 남 / 서
    # direction = [0, 1, 2, 3]
    if graph[x][y] == 0:
        count += 1
        graph[x][y] =2

    for _ in range(4):
        # 90도씩 왼쪽으로 회전하면서 청소할 곳이 있는지 확인
        nd = (d + 3) % 4
        nx, ny = x + dx[nd], y + dy[nd]
        if graph[nx][ny] == 0:
            # 청소
            dfs(nx, ny, nd)
            return
        d = nd

    # 청소되지 않은 빈 칸이 없는 경우
    nd = (d + 2) % 4
    nx, ny = x + dx[nd], y + dy[nd]
    # 후진 할 수 없으면 멈춤
    # 테두리는 모두 벽으로 둘러싸여 있으므로, 인덱스가 범위를 벗어날 경우는 고민하지 않아도 됨
    if graph[nx][ny] == 1:
        return
    dfs(nx, ny, d)

# main
n, m = map(int, input().split())

start_x, start_y, d = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

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

count = 0

dfs(start_x, start_y, d)

print(count)

1. 벽을 1로 둔다는 사실을 간과하고 0, 1로만 접근하려고 했고

2. 내가 이해했을 때는 청소기가 있는 위치에서 네 방면을 모두 확인한 후에 청소할 곳이 있다면 그제서야 90도 반시계 방향 회전을 하는 것으로 이해를 했는데, 생각해보니 말이 안되는 발상이긴 했다.

확인을 위해서는 반드시 회전을 거쳐야 할 것이고, 상식적으로 회전을 하는 도중에 청소가 되지 않은 부분을 확인하면 청소가 되는 것이 맞을 것이다.

코드 내 구현하는 방법은 비슷했으나, 문제를 잘못 이해했던 점이 아쉽다.

모든 정확한 답안은 문제를 정확하게 읽고 이해하는 데서 비롯된다는 점을 상기하자.

문제를 제대로 이해하지 않는다면 그 어떤 정답도 도출해낼 수 없다.