삼성SDS_백준14503_골드5_로봇 청소기 (시뮬레이션_구현_dfs_왼쪽 회전_뼈대 중요_다시풀어볼것)

• 링크 : https://www.acmicpc.net/problem/14503

---

메모

• 청소하는 영역의 수를 구해라

• n x m 행렬

  • 벽 또는 빈칸

• 청소기는 바라보는 방향이 있다

  • 방향 4개 : 동서남북
  • r, c는 청소기 처음 좌표 y, x

* 청소기 작동과정
1. 현재 위치 청소
2. 현재 위치에서 바라보고 있는 방향 기준으로 왼쪽부터 차례대로 탐색 진행   <--주의
    1. 그 왼쪽 방향에 아직 청소하지 않은 공간이 있으면
       - 그 방향으로 회전 - 한칸 전진 - 1번부터 진행(청소 후 바라보는 방향 왼쪽)
    
    2. 그 왼쪽 방향에 청소할 공간이 없으면
       - 그 방향으로 회전 - 2번부터 진행(청소 안하고 바라보는 방향 왼쪽)
    
    3. 동서남북 네 방향 모두 청소 되어있거나 or 벽이면
       - 바라보는 방향 그대로 유지 - 그상태로 한 칸 후진 - 2번부터 진행(청소 안하고 바라보는 방향 왼쪽)

    4. (동서남북 네 방향 모두 청소 되어있거나 or 벽이고) and 바라보는 방향의 두쪽이 벽이라서 후진할 수 없으면 종료

• 이미 청소된 칸은 청소할 수 없고, 벽을 통과할 수 없음

---

입력 설명

1. 세로 n, 가로 m
2. 로봇 청소기 위치 좌표(r, c), 방향 d

• d = 0 : 북
• d = 1 : 동
• d = 2 : 남
• d = 3 : 서

3. 청소할곳

• 1 : 벽
• 0 : 빈칸 (여기가 청소대상)

---

알고리즘 및 방법 - 내생각 (근데 틀림)

• 이거 DFS다
  • 갈수있을 때까지 쭉 가고, 2-4번케이스에 닥쳤을 때만 종료시키는데,
  • dfs 함수 한 번 탈 때마다 path++ 하면서 그때의 숫자를 리턴해야함

graph = 입력 n x m

# ++해주는 용도
#flag = True if graph[r][c] == 0 else False       # <-- 만약 시작점 1로 시작해서 바로 종료해야되는 테케 있으면 이거 다시 살려

graph[r][c] += 1       # 맨 처음 1번
dfs(r, c) 로 시작인데

def dfs(y, x, d):
    # 종료용
    if flag == True:
        continue
    
    # 2. 왼쪽부터 차례대로 탐색 진행
    if d == 0:              # 북쪽을 바라보면, 서쪽이 왼쪽이다
        ny, nx = y, x-1
        d = 3
    elif d == 1:            # 동쪽을 바라보면, 북쪽이 왼쪽이다
        ny, nx = y-1, x
        d = 0
    elif d == 2:            # 남쪽을 바라보면, 동쪽이 왼쪽이다
        ny, nx = y, x+1
        d = 1
    elif d == 3:            # 서쪽을 바라보면, 남쪽이 왼쪽이다
        ny, nx = y+1, x
        d = 2
        
    # 2-1) 회전 - 전진 - 1번부터
    if graph[ny][nx] == 0 and 0 <= ny and ny < n and 0 <= nx and nx < m:
        graph[ny][nx] = graph[y][x] + 1    # 1번 포함임
        dfs(ny, nx, d)
    
    # 2-2) 이동불가 -> 회전만 - 2번부터
    elif ny < 0 or n <= ny or nx < 0 or m <= nx:
        dfs(y, x, d)
        
    # 2-3) 이미 청소됨/벽 -> 방향 유지 - 후진 - 2번부터   <---이거 어떻게???
    elif graph[ny][nx] >= 1:        
        return
    
    # 2-4) 이미 청소됨 + 후진 불가 벽 - 끝
    elif graph[ny][nx] >= 1 and (ny < 0 or n <= ny or nx < 0 or m <= nx):
        flag = True
        return

---

솔루션 코드 - 내가 푼

• 오나전 잘못 접근
  • 나는 단순하게 문제에서 요구한 대로 dfs로 구현해야지 했는데
  • 생각보다 생각을 좀 깊게 했어야 했던..ㅎ

def dfs(y, x, d, flag):
    # 종료용
    if flag == True:
        return
    
    # 2. 왼쪽부터 차례대로 탐색 진행
    if d == 0:              # 북쪽을 바라보면, 서쪽이 왼쪽이다
        ny, nx = y, x-1
        d = 3
    elif d == 1:            # 동쪽을 바라보면, 북쪽이 왼쪽이다
        ny, nx = y-1, x
        d = 0
    elif d == 2:            # 남쪽을 바라보면, 동쪽이 왼쪽이다
        ny, nx = y, x+1
        d = 1
    elif d == 3:            # 서쪽을 바라보면, 남쪽이 왼쪽이다
        ny, nx = y+1, x
        d = 2
        
    # 2-1) 회전 - 전진 - 1번부터
    if graph[ny][nx] == 0 and 0 <= ny and ny < n and 0 <= nx and nx < m:
        graph[ny][nx] = graph[y][x] + 5    # 1번 포함임
        dfs(ny, nx, d, flag)
    
    # 2-2) 이동불가 -> 회전만 - 2번부터
    elif ny < 0 or n <= ny or nx < 0 or m <= nx:
        dfs(y, x, d, flag)
        
    # 2-3) 이미 청소됨/벽 -> 방향 유지 - 후진 - 2번부터   <---이거 어떻게???
    elif graph[ny][nx] >= 1:        
        return
    
    # 2-4) 이미 청소됨 + 후진 불가 벽 - 끝
    elif graph[ny][nx] >= 1 and (ny < 0 or n <= ny or nx < 0 or m <= nx):
        flag = True
        ans = graph[ny][nx]
        print("---->",ans)
        return
    
n, m = map(int, input().split())

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

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

ans = 100

graph[r][c] = 1       # 맨 처음 1번    
dfs(r, c, d, False)
print(graph)
print(ans)

---

솔루션 코드 - 블로그 (중요)

• 출처 : https://wewinserv.tistory.com/173

• 사실상 1번) 현재 위치를 청소한다 <-- 훼이크임

  • 맨 첨에 시작점만 1로 변경해주고
  • 2-1번 수행할 때 다음 이동에서 ++해주기 때문에...!

• (중요) turn_left()함수에 집중하자

  • 북-동-남-서 방향을 지정해준 이유가 있었음
    • global direction에서 -1할 때마다 왼쪽방향을 보게 되어있음
    • 이거에 맞춰서 dy, dx도 유지!

• 코드 원본

n, m = map(int,input().split()) # N, M을 입력 받음

d =[[0] * m for _ in range(n)] # 청소 여부를 list로 생성
x, y, direction = map(int,input().split()) # x, y, direction를 입력 받음
d[x][y] = 1 # 현재 위치 청소 (0->1)

array = [] # 빈 칸, 벽을 입력 받음
for i in range(n): # n 개의 rows에 대해서 각 row의 입력을 받음
    array.append(list(map(int,input().split()))) #입력은 list 형태로 array에 append

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

# 0: 위쪽 이동, 1: 오른쪽 이동, 2: 아래 이동, 3: 왼쪽 이동

def turn_left(): # 왼쪽으로 트는 함수
    global direction # global 함수 선언
    direction -= 1 # 왼쪽으로 이동
    # 0 : 북, 1 : 동, 2 : 남, 3 : 서
    if direction == -1: # 음수가 되는 경우, 
        direction = 3 # 3으로 초기화

count = 1 # 현재 위치를 청소 했음으로 1
turn_time = 0 # 왼쪽 방향으로 회전하는 횟수 계산, 4번인 경우 다른 조건 실행
while True:
    turn_left() # 왼쪽 방향으로 회전
    nx = x+ dx[direction] # 현재 방향으로 이동
    ny = y+ dy[direction] # 현재 방향으로 이동

    if d[nx][ny] == 0 and array[nx][ny] == 0: # 이동을 했는데, 방문하지 않았거나, 빈 공간인 경우
        d[nx][ny] = 1 # 이동한 위치에서 청소, 0->1
        x = nx # 위치 이동
        y = ny # 위치 이동
        count += 1 # 청소를 했음으로 1 증가
        turn_time = 0 # 왼쪽 방향 회전 횟수 0으로 초기화
        continue # 반복

    else: # 이동이 불가능 한 경우 왼쪽 방향 회전, 횟수 증가
        turn_time += 1

    if turn_time == 4: # 총 4번 회전 한 경우, 네 방향 모두 청소가 되어 있거나 벽이 있는 경우
        nx = x-dx[direction] # 바라보는 방향에서 뒤로 이동
        ny = y-dy[direction] # 바라보는 방향에서 뒤로 이동

        if array[nx][ny] == 0: #이동한 위치가 벽이 아니라면,
            x = nx # 이동
            y = ny # 이동

        else: # 그렇지 않으면,
            break # 작동을 멈춤
        turn_time = 0 # 왼쪽 방향 회전 횟수 초기화

print(count) # count 값 출력

• 2번 테케의 visit배열 (여기선 d배열)

[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
 [0, 1, 1, 1, 0, 0, 0, 0, 1, 0], 
 [0, 1, 1, 0, 0, 1, 1, 1, 1, 0], 
 [0, 1, 0, 0, 1, 1, 1, 1, 0, 0], 
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
 [0, 1, 1, 1, 1, 1, 0, 0, 1, 0], 
 [0, 1, 1, 1, 1, 1, 0, 0, 1, 0], 
 [0, 1, 1, 1, 1, 1, 0, 0, 1, 0], 
 [0, 1, 1, 1, 1, 1, 1, 1, 1, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

• 내가 이해하기 위해 정리한 코드
  • 근데 복붙하는 과정에서 답이 다르게 나옴;;
  • 그냥 주석 통해서 프로세스 이해용으로 사용하자

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

visit = [[0] * m for _ in range(n)]    # visit 배열

y, x, direction = map(int, input().split())

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

# 왼쪽 방향으로 회전하는 횟수 계산 (4번인 경우 다른 조건을 실행한다) ~> 일종의 Flag
turn_time = 0

#     북  동  남  서   (개중요) {동쪽방향을 볼 때 왼쪽은 북쪽!} "똑같이 맞춰줘야함!"
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]

# 왼쪽으로 트는 함수
def turn_left():
    global direction   # (중요) 글로벌 선언
    direction -= 1     # (개중요) 0 : 북  <-  1 : 동  <-  2 : 남  <-  3 : 서   {동쪽방향을 볼 때 왼쪽은 북쪽!}
    
    # (중요) 음수가 되면 3으로 초기화 (북동남서 로테이션!!!)
    if direction == -1:
        direction = 3
    
# 청소 횟수 카운트 (나는 dfs 할 생각 했는데... 이래도 되네...)
count = 1
visit[y][x] = 1
while True:
    # 2) 왼쪽 방향으로 회전
    turn_left()
    
    ny = y + dy[direction]
    nx = x + dx[direction]
    
    # 2-1) 첫 방문인 경우 - 이동 - 청소 - 방향 튼다(다음 loop에서)
    if graph[ny][nx] == 0 and visit[ny][nx] == 0:
        visit[ny][nx] = 1 # (현재 위치 청소)
        
        # 위치 이동
        y = ny
        x = nx
        
        count += 1
        turn_time = 0   # 왼쪽 방향 회전 횟수 0으로 초기화
        continue       # 다음 loop으로
        
    # 2-2) 이동 불가한 경우 - 회전만
    else:
        turn_time += 1
        
    # 2-3) 네 방향 모두 청소가 되었다. or 벽이 있는 경우 (2-1, 2-2와 별도로 작동 케이스)
    if turn_time == 4:
        # (중요) 후진!!!!!!!!!!!!!!!
        ny = y - dy[direction]
        nx = x - dx[direction]
        
        # 2-3) 이동 위치가 벽이 아니라면 - 후진
        if visit[ny][nx] == 0:
            y = ny
            x = nx
        # 4) 프로그램 종료
        else:
            break
        turn_time = 0
        
print(count)