엠비티아이 - 24725

24725번: 엠비티아이

이렇게 랜덤 알파벳이 적힌 $N*M$ 보드가 주어지고, 안에서 엠비티아이 글자를 몇 개 찾을 수 있는지 구하는 문제

시행 착오 1 🥲

생각보다 구현하는게 너무 어려웠다. 먼저 생각해본 알고리즘은

• E/I에 해당하는 좌표에서 dfs(깊이 우선 탐색) 진행하는 것 !

dfs는 모든 좌표를 탐색할 때까지 진행한다는게 첫번째 문제점이었고, 게다가 dfs 함수에 8 방향으로 탐색하도록 구현하니까 얘가 방향을 자유재로 꺾는다. 직선 한 방향으로만 탐색하도록 조건을 또 걸어주려다가 코드가 너무 복잡해져서 결국 실패한 방법

-> 조오금만 더 손보면 풀릴 수 있을 것 같긴 하다 ,,

맞았습니다! 풀이

결국 팀원분 코드를 참고해서 풀었다.

• 모든 좌표에 대해서 E/I, S/N, F/T, P/J 순서로 된 문자가 있는지 확인

찾아보니 파이썬에 regular expression을 구현할 수 있는 re 라이브러리가 있었다! 이걸 사용하면 mbti를 정규 표현식으로 구현해놓고 여기에 해당되는지 체크만 해주면 돼서 완전 간단하게 구현할 수 있다.

import re
N, M = map(int, input().split())
board = [input() for _ in range(N)]

res = 0
mbti = re.compile('(E|I)(N|S)(F|T)(P|J)|(P|J)(F|T)(N|S)(E|I)')

for i in range(N):
  for j in range(M):
    if i+3 < N and mbti.match(board[i][j]+board[i+1][j]+board[i+2][j]+board[i+3][j]):
      res += 1  # 세로 
    if j+3 < M and mbti.match(board[i][j]+board[i][j+1]+board[i][j+2]+board[i][j+3]):
      res += 1  # 가로
    if i+3 < N and j+3 < M and mbti.match(board[i][j]+board[i+1][j+1]+board[i+2][j+2]+board[i+3][j+3]):
      res += 1  # 대각선 오른쪽 위
    if i+3 < N and j-3 >= 0 and mbti.match(board[i][j]+board[i+1][j-1]+board[i+2][j-2]+board[i+3][j-3]):
      res += 1  # 대각선 왼쪽 위 

print(res)

맨 위로 이동하기