청소하는 영역의 수를 구해라
n x m 행렬
청소기는 바라보는 방향이 있다
* 청소기 작동과정
1. 현재 위치 청소
2. 현재 위치에서 바라보고 있는 방향 기준으로 왼쪽부터 차례대로 탐색 진행 <--주의
1. 그 왼쪽 방향에 아직 청소하지 않은 공간이 있으면
- 그 방향으로 회전 - 한칸 전진 - 1번부터 진행(청소 후 바라보는 방향 왼쪽)
2. 그 왼쪽 방향에 청소할 공간이 없으면
- 그 방향으로 회전 - 2번부터 진행(청소 안하고 바라보는 방향 왼쪽)
3. 동서남북 네 방향 모두 청소 되어있거나 or 벽이면
- 바라보는 방향 그대로 유지 - 그상태로 한 칸 후진 - 2번부터 진행(청소 안하고 바라보는 방향 왼쪽)
4. (동서남북 네 방향 모두 청소 되어있거나 or 벽이고) and 바라보는 방향의 두쪽이 벽이라서 후진할 수 없으면 종료
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
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)
사실상 1번) 현재 위치를 청소한다 <-- 훼이크임
(중요) turn_left()함수에 집중하자
코드 원본
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 값 출력
[[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)