💡 문제
십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크거나 같아야 한다.
아래 그림은 크기가 1, 2, 3인 십자가이고, 빈 칸은 '.'이다.
크기가 N×M이고, '.'과 '*'로 이루어진 격자판이 주어진다. 이때, 십자가만을 이용해서 격자판과 같은 모양을 만들 수 있는지 구해보자. 십자가는 서로 겹쳐도 된다. 사용할 수 있는 십자가의 개수는 N×M이하이어야 한다. 격자판의 행은 위에서부터 1번, 열은 왼쪽에서부터 1번으로 번호가 매겨져 있다.
입력
첫째 줄에 격자판의 크기 N, M (3 ≤ N, M ≤ 100)이 주어진다. 둘째 줄부터 N개의 줄에 격자판의 상태가 주어진다.
출력
십자가만 이용해서 입력으로 주어진 격자판을 만들 수 없으면 -1을 출력한다.
만들 수 있는 경우에는 필요한 십자가의 수 k(0 ≤ k ≤ N×M)를 출력한다. 다음 k개의 줄에는 그려야 하는 십자가의 정보 x, y, s를 한 줄에 하나씩 출력한다. x는 십자가 중심의 행의 번호, y는 열의 번호, s는 십자가의 크기이다.
가능한 답이 여러가지인 경우에는 아무거나 출력한다.
💭 접근
이 문제를 해결하기 위해서 다음과 같은 순서를 따른다.
-
먼저 입력으로 주어진 격자판을 순회하며
*을 만나면 그 점을 중심으로 4방향이 모두*인지 탐색한다. (이때 길이는 1로 시작하며, 4방향이 모두*라면 이 좌표는 십자가의 중심이 된다. -
1단계에서 4방향이 모두
*이었다면 비어있는empty_arr격자판에 해당 길이의 십자가를 그리고ans리스트에 십자가의 위치와 길이를 저장한다. 이후, 길이를 +1하며 더 큰 십자기를 그릴 수 있는지 확인한다. -
1단계에서 4방향이 모두
*이 아니라면 십자가의 중심이 아닌 것이므로 건너뛴다.
1, 2, 3번 코드
for i in range(n):
for j in range(m):
if arr[i][j] == '*':
length = 1
break_flag = False
while True:
break_flag = check(i, j, length)
if break_flag:
break
else:
ans.append([i + 1, j + 1, length])
empty_arr[i][j] = '*'
draw(i, j, length)
length += 1현재 좌표가 십자가의 중심인지 판단하는 함수
def check(x, y, length):
for i in range(4):
nx = x + dx[i] * length
ny = y + dy[i] * length
if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == '*':
pass
else:
return True
return False현재 좌표가 십자가의 중심일 때 십자가를 그리는 함수
def draw(x, y, length):
for i in range(4):
nx = x + dx[i] * length
ny = y + dy[i] * length
empty_arr[nx][ny] = '*'-
위 단계를 모두 마치고 (입력으로 주어진 격자판을 모두 순회하고) 입력으로 주어진 격자판과 새로 그린 격자판을 비교한다.
-
입력으로 주어진 격자판과 새로 그린 격자판이 동일하다면 정답을 출력하고, 다르다면 -1을 출력한다.
📒 코드
def check(x, y, length):
for i in range(4):
nx = x + dx[i] * length
ny = y + dy[i] * length
if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == '*':
pass
else:
return True
return False
def draw(x, y, length):
for i in range(4):
nx = x + dx[i] * length
ny = y + dy[i] * length
empty_arr[nx][ny] = '*'
n, m = map(int, input().split())
arr = [list(input()) for _ in range(n)]
empty_arr = [['.' for _ in range(m)] for _ in range(n)]
ans = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
for j in range(m):
if arr[i][j] == '*':
length = 1
break_flag = False
while True:
break_flag = check(i, j, length)
if break_flag:
break
else:
ans.append([i + 1, j + 1, length])
empty_arr[i][j] = '*'
draw(i, j, length)
length += 1
for i in range(n):
if arr[i] != empty_arr[i]:
print(-1)
break
else:
print(len(ans))
for i in range(len(ans)):
print(*ans[i])💭 후기
입력으로 주어진 격자판을 순회하며 가능한 십자가를 모두 그려보며 가능한지 판단하는게 핵심이었던 문제.
🔗 문제 출처
https://www.acmicpc.net/problem/16924
