문제 링크 : https://www.acmicpc.net/problem/15705
1. Constraints (제한 사항)
- 알고리즘 문제와 요구와 제한사항
문제
N×M 크기의 표의 각 칸에 알파벳 대문자가 하나씩 쓰여 있다.
단어 S가 주어졌을 때, 표에 단어 S가 있는지 없는지 구하는 프로그램을 작성하시오.
단어 S가 표에 존재하려면, 표의 한 칸에서 시작해, 연속해서 그 단어의 모든 알파벳이 순서대로 등장해야 한다. 이때, 연속하는 방향은 위, 아래, 오른쪽, 왼쪽, 대각선 방향 모두 가능하다. 대각선 방향은 왼쪽 위, 오른쪽 아래, 오른쪽 위, 왼쪽 아래 방향이 모두 가능하다. 연속하는 방향이 중간에 바뀌면 안 된다.
입력
첫째 줄에 길이가 100보다 작거나 같은 단어 S가 주어진다.
S는 알파벳 대문자로만 이루어져 있다.
둘째 줄에는 표의 행의 개수 N과 열의 개수 M이 주어진다.
N과 M은 100보다 작거나 같은 자연수이다.
셋째 줄부터 N개의 줄에는 표의 각 행에 들어있는 알파벳이 주어진다.
출력
입력으로 주어진 표에 단어 S가 존재하면 1을, 없으면 0을 출력한다.
제한
시간 제한 = 2초 (pypy3 : 12초)
메모리 제한 = 512MB
나의 생각
- M x N 개의 알파벳이 들어있는 배열 (최대 10000개)
- 문자열의 길이도 100자 이하
- 배열에서 갈 수 있는 방향은 8가지
- 연속하는 방향이 중간에 바뀌면 안된다는 것을 기억
2. Ideas (문제 풀이 방식)
- 문제를 해결할 수 있는 방법 (최대 3개) + 시간/공간 복잡도
(1) 브루트포스
: 2차원 배열의 모든 원소를 순회하면서 프로그램을 수행하는데
만약 문자열[0]과 현재 원소가 같다면 answer에 1을 저장하고
8가지 방향으로 나아가본 뒤
문자열과 타겟 문자가 같을 때마다 1을 더한다.
모두 끝났을 때 answer와 len(S)이 같다면 문자열을
찾은 것이므로 1을 return하고
중간에 return하지 못하면 찾지 못한 것이므로 0을 return한다.
시간 복잡도 : O(MN x len(S))
공간 복잡도 : O(1)
- 최대 100 x 100 x 8 x 100 = 8,000,000번 연산
3. Code (작성한 코드)
- 아이디어에서 다룬 내용을 바탕으로 구현한 코드
def exist(target: str, row: int, col: int, board: list[list[str]]) -> bool:
directions = [
[ 1, 1], # 대각선 오른쪽 아래
[ 1, 0], # 아래
[ 1, -1], # 대각선 왼쪽 아래
[ 0, 1], # 오른쪽
[ 0, -1], # 왼쪽
[-1, 1], # 대각선 오른쪽 위
[-1, 0], # 위
[-1, -1], # 대각선 왼쪽 위
]
for i in range(row):
for j in range(col):
if board[i][j] == target[0]:
for direction in directions:
x, y = i, j
answer = 1
for i in range(1, len(target)):
x += direction[0]
y += direction[1]
if x < 0 or x > row-1:
break
if y < 0 or y > col-1:
break
if board[x][y] != target[i]:
break
answer += 1
if answer == len(target): return 1
return 0# 백준이라서 사용한 입출력 툴
target = str(input())
M, N = map(int, input().split())
board = [ str(input()) for _ in range(M) ]
print(exist(target, M, N, board))4. Test cases (테스트케이스)
- 테스트 케이스에 대해서 고민해보고, 직접 테스트해보기
ABCD
5 5
ACDBE
ABCED
ACCEE
ACHDF
ACBCE
출력 : 1 (맞음)
STR
6 6
STARTS
STRSTR
RRTSRE
SRSTRR
STRTSR
STSTSS
출력 : 1 (맞음)
AFAFK
2 2
AB
CD
출력 : 0 (맞음)
AAAB
4 4
AAAA
ABBA
ABBA
AAAA
출력 : 0 (맞음)
테스트 케이스도 다 맞으니 제출해보도록 하자.
7%까지 올라가다 틀렸습니다를 마주하였다.
고통과 인내의 시간이다.
5. 다시 생각하기
무엇이 잘못되었을까?
한 20분 고민하였나? 원래 2시간 고민하라고 적혀있지만
이건 20분이나 2시간이나 똑같을 것 같은 느낌이 들어
반례를 만들기로 했다.
모든 경우의 수를 만들고 있었다.
근데 이게 웬 걸... 벌써 여기서부터 오류가 나는 것이다.
ABC
3 3
ABC
ZZZ
ZZZ
도대체 이게 왜 틀린거지 하고
print()를 여기저기 붙여 디버깅을 하다 실수를 발견하였다.
for i in range(1, len(target)):바로 이 코드에서 오류가 났던 것이었다.
위에서 사용한 변수 이름을 재사용하니 이런 일이 발생하는 것이었다.
k로 고쳐주니 8개의 모든 테스트 케이스가 올바르게 출력되었다.
(아니 이전 테스트 케이스는 어떻게 통과한 거야 이걸로)
def exist(target: str, row: int, col: int, board: list[list[str]]) -> bool:
directions = [
[ 1, 1], # 대각선 오른쪽 아래
[ 1, 0], # 아래
[ 1, -1], # 대각선 왼쪽 아래
[ 0, 1], # 오른쪽
[ 0, -1], # 왼쪽
[-1, 1], # 대각선 오른쪽 위
[-1, 0], # 위
[-1, -1], # 대각선 왼쪽 위
]
for i in range(row):
for j in range(col):
if board[i][j] == target[0]:
for direction in directions:
x, y = i, j
answer = 1
for k in range(1, len(target)):
x += direction[0]
y += direction[1]
if x < 0 or x > row-1:
break
if y < 0 or y > col-1:
break
if board[x][y] != target[k]:
break
answer += 1
if answer == len(target): return 1수정한 코드이다. 변수이름을 잘 확인하자...
Python Tutor
알고리즘이 그렇게 어렵지 않아서 Tutor 없이도 이해할 수 있을 것 같다.
마무리
변수 이름을 잘 사용하자.
