파이썬 몬스터 트럭(백준 BOJ 2897)
문제
해빈이가 드디어 면허를 땄다! 해빈이의 부모님은 기뻐하며 해빈이에게 첫 차로 몬스터 트럭을 사 주셨다. 해빈이는 자신의 첫 차가 강남 대로의 모든 차를 부수면서 러시 아워조차 자신을 막을 수 없다는 것을 깨닫고 기뻐했지만, 차가 다른 차들의 네 배 크기이기 때문에 주차하는 데 애를 먹고 있었다.
그걸 본 준규는 마침 강남에서 공영 주차장 아르바이트를 하고 있기 때문에 정기적으로 해빈이에게 강남 주차장 지도를 보내주기로 했다. 지도는 R행 C열의 표로 이뤄져 있다. 표의 각 칸은 빌딩(‘#’), 주차 된 차(‘X’), 또는 빈 주차 공간(‘.’)이다. 해빈이의 차는 꽤 커서 정확히 2행 2열의 칸을 차지한다.
해빈이를 도와 가능한 주차 공간을 해빈이가 부숴야 하는 차의 수대로 모아서 보여주자. 이때 주차하기 위해 부숴야 하는 차만 고려한다. (주차 하러 가는 길에 부수는 차는 신경쓰지 않는다.) 단, 아무리 몬스터 트럭이라도 빌딩을 부술 수는 없기 때문에 빌딩이 있는 자리에는 주차를 할 수 없다.
입력
입력의 첫 줄에 두 정수 R과 C(2 ≤ R, C ≤ 50)가 주어진다. R은 행의 개수, C는 열의 개수이다.
두 번째 줄에는 R개의 줄에 각각 C개의 문자가 주어진다. 이 문자는 ‘#’, ‘X’, ‘.’로만 이뤄져 있다. ‘X’는 항상 영대문자이다.
출력
출력은 다섯 줄이다. 첫째 줄에는 해빈이가 아무 차도 부수지 않으면서 주차할 수 있는 공간의 개수, 둘째 줄은 차 한 대를 부수고 주차할 수 있는 공간의 개수, 셋째 줄은 차 두 대, 넷째 줄은 차 세 대, 다섯째 줄은 차 네 대를 부수고 주차할 수 있는 공간의 개수이다.
예제 입력 1
4 4
#..#
..X.
..X.
#XX#
예제 출력 1
1
1
2
1
0
예제 입력 2
4 4
....
....
....
....
예제 출력 2
9
0
0
0
0
예제 입력 3
4 5
..XX.
.#XX.
..#..
.....
예제 출력 3
2
1
1
0
1
📝 풀어보기
📌 문제에서 혜빈이의 차는 2*2 사이즈다. 찍은 좌표에서 우측, 우하측, 하측을 탐색해서 2*2 범위 내의 장애물을 찾는다. 델타 탐색을 위해 변수를 선언하고 빌딩은#, 자동차는X, 빈공간은.로 지정한다.
# 우 우하 하
# x+1 ,(y+1,x+1), y+1
dr = [0, 1, 1]
dc = [1, 1, 0]
BUILDING = "#"
CAR = "X"
VOID = "."
📌 행의 개수 R, 열의 개수 C를 입력받는다.
R의 범위동안 리스트를 입력받아 생성한 리스트에 저장한다. 문제에서 출력 줄마다 차를 부숴가며 주차할 수 있는 공간의 개수를 요구하므로 부순 횟수를 저장할 리스트를 생성한다.
# 숫자가 공백으로 나뉘어져있는 입력
R, C = list(map(int, input().split()))
list_ = []
# R 줄 만큼의 리스트를 입력
for _ in range(R):
# 숫자 X 문자 O
# 공백 X
temp_list = list(input())
list_.append(temp_list)
# 부순 횟수를 저장할 리스트
# 0개 1개 2개 3개 4개 부순횟수를 저장
break_count_list = [0] * 5
📌 열과 행의 범위를 반복하면서 리스트 내의 기준 좌표가 빌딩이면 건너뛴다. 리스트 내의 기준 좌표가 차면 부순 횟수를 1 증가시킨다.
# 이중 반복문
for r in range(R):
for c in range(C):
# 차를 부순 횟수는 탐색을 할 때마다 초기화(0)
break_count = 0
# 조건 1. 기준 좌표가 빌딩(#)이면 안된다.
if list_[r][c] == BUILDING:
# 이 다음 반복문의 코드들을 무시하고, 다음 값을 탐색
continue
# 성립이 안되는 조건들은 continue로 지나가고,
# 조건이 성립될 때만 정상적인 코드를 실행한다.
# 조건 2. 기준 좌표가 차라면 부순 횟수 + 1
if list_[r][c] == CAR:
break_count += 1
📌 델타탐색을 수행한다. dr, dc 리스트 내의 요소를 순회하면서 열과 행에 추가하고 합산된 값이 -1과 R 범위 내에 없으면 반복을 빠져나온다.
탐색 좌표에 빌딩이 있으면 안되므로 빌딩이 있는 경우에도 빠져나온다.
탐색 좌표에 차가 있으면 부순 횟수를 1증가시킨다.
break를 만나지 않고 for문이 끝난 경우는 정상적으로 주차를 했다는 얘기이므로 break_count_list[0]을 1 증가시켜준다.
마지막으로 break_count_list를 순회하면서 count를 출력한다.
"""
델타탐색을 하는 로직
"""
for d in range(3):
next_r = r + dr[d]
next_c = c + dc[d]
# 조건 1. 범위를 벗어나면 안된다.
if not (-1 < next_r < R and -1 < next_c < C):
break
# 조건 2. 탐색 좌표에 빌딩이 있으면 안된다.
if list_[next_r][next_c] == BUILDING:
break
# 조건 3. 탐색 좌표에 차가 있으면 부순 횟수를 + 1
if list_[next_r][next_c] == CAR:
break_count += 1
# break를 만나지 않고 for문이 끝났다면
# 혜빈이가 정상적으로 주차를 했다
else:
break_count_list[break_count] += 1
# print(break_count_list)
# 정답 출력
for count in break_count_list:
print(count)
전체 코드
# 우 우하 하
# x+1 ,(y+1,x+1), y+1
dr = [0, 1, 1]
dc = [1, 1, 0]
BUILDING = "#"
CAR = "X"
VOID = "."
# 숫자가 공백으로 나뉘어져있는 입력
R, C = list(map(int, input().split()))
list_ = []
# R 줄 만큼의 리스트를 입력
for _ in range(R):
# 숫자 X 문자 O
# 공백 X
temp_list = list(input())
list_.append(temp_list)
# 부순 횟수를 저장할 리스트
# 0개 1개 2개 3개 4개 부순횟수를 저장
break_count_list = [0] * 5
# 이중 반복문
for r in range(R):
for c in range(C):
# 차를 부순 횟수는 탐색을 할 때마다 초기화(0)
break_count = 0
# 조건 1. 기준 좌표가 빌딩(#)이면 안된다.
if list_[r][c] == BUILDING:
# 이 다음 반복문의 코드들을 무시하고, 다음 값을 탐색
continue
# 성립이 안되는 조건들은 continue로 지나가고,
# 조건이 성립될 때만 정상적인 코드를 실행한다.
# 조건 2. 기준 좌표가 차라면 부순 횟수 + 1
if list_[r][c] == CAR:
break_count += 1
"""
델타탐색을 하는 로직
"""
for d in range(3):
next_r = r + dr[d]
next_c = c + dc[d]
# 조건 1. 범위를 벗어나면 안된다.
if not (-1 < next_r < R and -1 < next_c < C):
break
# 조건 2. 탐색 좌표에 빌딩이 있으면 안된다.
if list_[next_r][next_c] == BUILDING:
break
# 조건 3. 탐색 좌표에 차가 있으면 부순 횟수를 + 1
if list_[next_r][next_c] == CAR:
break_count += 1
# break를 만나지 않고 for문이 끝났다면
# 혜빈이가 정상적으로 주차를 했다는 소리
else:
break_count_list[break_count] += 1
# print(break_count_list)
# 정답 출력
for count in break_count_list:
print(count)