코드

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

r, c, d = map(int, input().split())

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

def solution(r, c, d):   
    
    # 방문 여부를 담을 리스트
    # 이 문제는 방문을 하면 무조건 청소를 함
    # 따라서 이 리스트가 없으면
    # 중복해서 청소하는 구역이 발생함
    visited = [[False for _ in range(m)] for _ in range(n)]

    # 북 동 남 서 좌표 방향
    # 아래의 nd와 함께 조합하여
    # 다음 좌표 nr, nc를 구함
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]    

    # 시작점 청소 완료
    visited[r][c] = True

    # 청소 구역 담을 변수(시작점에 따라 +1)
    cnt = 1
    
    # 무한 반복 수행
    while True:

        # 청소 여부를 담을 불린 변수
        # 4방향을 돌았는데도 청소를 못한 경우를 체크하기 위함
        # 위의 경우가 곧 탈출 조건
        check = False

        # 4방향 탐색
        for _ in range(4):

            # 왼쪽으로 돌렸을 때 바라보는 방향
            # ex) 북 (0) => 서 (3)
            #     (0 + 3) % 4 => 3 ==> 서
            d = (d + 3) % 4
            
            # 왼쪽 방향으로 전진
            nr = r + dr[d]
            nc = c + dc[d]

            # 범위를 벗어나면 생략
            if nr < 0 or nr >= n or nc < 0 or nc >= m:
                continue

            # 값이 0 => 빈 칸 (이동 가능)
            if graph[nr][nc] == 0:
                
                # 방문한 적이 없으면
                if visited[nr][nc] == False:
                    
                    # 방문 처리
                    visited[nr][nc] = True
                    
                    # 개수 1 증가
                    cnt += 1

                    # 다음 좌표로 이동했음
                    # r, c를 초기화
                    r = nr
                    c = nc

                    # 청소 완료
                    check = True
                    break

        # 4방향 모두 돌았는데, 청소할 수 없는 경우
        if check == False:
            # 후진했는데 벽인 경우 (작동 멈추는 조건)
            if graph[r-dr[d]][c-dc[d]] == 1:
                return cnt
            # 후진했는데 벽이 아니므로 후진 가능
            else:
                r -= dr[d]
                c -= dc[d]
                
print(solution(r, c, d))

문제 해설

구현 문제.

다른 문제들과 다르게 그냥 코드만 줄줄 짜면 되지만 정말 어렵고 생각할 것들이 너무 많은 문제 유형. 이것도 다 꾸준하게 천천히 꼼꼼하게 푸는 버릇이 안 들어서 그런 것 같다 ㅠㅠ

문제의 핵심 로직은 아래와 같다.

1. 로봇은 항상 왼쪽으로 회전함

  • # 북 동 남 서 좌표 방향
# 아래의 nd와 함께 조합하여
# 다음 좌표 nr, nc를 구함
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]  
  
# 왼쪽으로 돌렸을 때 바라보는 방향
# ex) 북 (0) => 서 (3)
#      (0 + 3) % 4 => 3 ==> 서
d = (d + 3) % 4

  • 예시에서 본 것과 같이 북쪽을 바라보면서 왼쪽으로 턴하면 서쪽이다,

  • 왼쪽으로 돌아서 전진하는 경우는 x 또는 y 중 하나의 값만 변경된다.

    • dr, dc가 교차로 0을 가지고 있는 이유
  • 기존 d를 (d + 3) % 4로 계산해주면 dr, dc에서 알맞은 방향으로 r, c의 값을 업데이트 할 수 있다.

2. visited 리스트가 없으면 안됨

  • 처음visited 리스트의 존재 이유를 사실 잘 몰랐다. 하지만 문제에 버젓히 적혀 있듯이, 이 로봇은 방문할 수 있는 곳은 무조건 청소를 하고 후진도 하기 때문에 중복하여 청소하는 지역이 발생한다. 따라서 check라는 불Boolean 값은 탈출 조건으로 쓰이고, visited 리스트는 청소 여부만 판단하는 용도로 사용된다.

3. r - dr[d], c - dc[d]는 후진임

  • 이는 생각해보면 간단한 팁일 수도 있으나, 정말 중요하다. (후진하는 경우가 탈출 조건임)

위처럼 꼼꼼하게 조건을 따져가면서 천천히 코드로 구현하면 해결할 수 있는 문제. 물론 구글링의 도움을 받았지만… 한 번도 아니고 여러번 꾸준하게 반복하여 풀면서 코드를 디테일하고 논리적이게 짜는 연습을 할 수 있는 좋은 문제인 것 같다.`

댓글남기기

참고