[ 백준 / BOJ ] 16924 십자가 찾기

/  제출 1  /

 

n, m = map(int, input().split())
answer = []
board = []
# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
cannot = []
for i in range(n):
  board.append(list(input().strip()))
for x in range(n):
  for y in range(m):
    if board[x][y] == '*':
      size = 1
      check = True
      while check:
        # check 4 directions
        for i in range(4):
          nx = x + dx[i] * size
          ny = y + dy[i] * size
          if nx < 0 or n <= nx  or ny < 0 or m <= ny or board[nx][ny] == '.':
            check = False
            size -= 1
        if check:
          size += 1
        else:
          if size >= 1:
            while size > 0:
              answer.append([x, y, size])
              size -= 1

for ans in answer:
  x, y, size = ans
  while size > 0:
    for i in range(4):
      nx = x + dx[i] * size
      ny = y + dy[i] * size
      if not(nx < 0 or n <= nx  or ny < 0 or m <= ny):
        
        if board[nx][ny] == '*':
          board[nx][ny] = '.'
        board[x][y] = '.'
    size -= 1
    
possible = True
for i in range(n):
  for j in range(m):
    if board[i][j] == '*':
      possible = False
      
if possible:  
  print(len(answer))
  for i in range(len(answer)):
    x, y, size = answer[i]
    print(x+1, y+1, size)
else:
  print(-1)

하.. 채점만 18분.. 효율성 극악.. 코드를 만들었나봅니다.

 

집념의 풀이.. 축하합니다 나 자신 ^.^

 

1차 문제 해결 27분 걸리고, 오류 나서 수정했습니다.

(nx, ny)를 체크할 때 범위 설정을 반대로 해줬던 문제 바로잡았습니다.

왜 오류였는지 찾는데 은근 오래 걸렸습니다. 문제해결 핵심 부분이 아니라서 무신경해서였습니다.

 

 

2차 문제 해결 48분 걸렸습니다. 예제 테케 4개 중 3번째 문제에서 답이 원하는 대로 나오지 않았습니다.

그냥 십자가를 찾아내는게 아니라 십자가를 이용해 주어진 격자판을 만들 수 있니? 가 주요 문제고,

있을 때 십자가도 말해줘!가 부수문제였기 때문입니다. 

저는 문제 풀며 두 번째에 집중했기에 2차 문제 해결에서 오류 테케가 있었던 것이었습니다.

 

 

만약 히든테케 문제였다면 틀림 없이 틀렸겠죠.. 여러가지로 생각해보고 문제 구현, 테케 확실히 잘 정의하기로 합시다.

 

하여간 해당 문제는 찾아낸 십자가를 이용해 맵을 재구성하는 부분을 추가했습니다.

십자가만큼 지우고 남은 보드에서 * 이 남아있다면 십자가로는 해당 보드를 못 만든다는 아이디어입니다.

 

 

좋은 풀이는 아닐 것 같다는 생각은 풀면서도 들었지만, 제출 후에 확신했습니다.

채점에 18분이 소요되었기 때문입니다. 몇%에서 혹시 틀려버릴까 궁금해 냅다 기다렸는데, 결국 다 통과하긴 했습니다.

시간초과도 안 났고요. 아슬아슬하게 넘긴 것 같습니다.

 

다른 분들 풀이를 보고 개선점을 많이 찾아봐야겠습니다.

 

 

효율적이지는 않더라도 격자판 구현문제인데 (약점) 1시간 2분안에 제출+통과했다는 점에서 나름 안도했던 문제였습니다.

 

---

/  다른 분들 풀이  /

 

일단 시간이 미친듯이 오래 걸린 이유는 데이터를 받을 때 input()으로 받았기 때문이었습니다.

sys를 import해서 sys.stdin.readline()으로 데이터를 받도록 바꿔주니 시간이 약간 빨라졌습니다.