[백준] [파이썬] 15705번: 단어찾기

문제집 추천, 이 문제집에 나온 유형들만 공부해도 코딩테스트는 거뜬: https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

15705번: 단어찾기 문제보러가기

15705번: 단어 찾기

 

문제

N×M 크기의 표의 각 칸에 알파벳 대문자가 하나씩 쓰여 있다. 단어 S가 주어졌을 때, 표에 단어 S가 있는지 없는지 구하는 프로그램을 작성하시오.

단어 S가 표에 존재하려면, 표의 한 칸에서 시작해, 연속해서 그 단어의 모든 알파벳이 순서대로 등장해야 한다. 이때, 연속하는 방향은 위, 아래, 오른쪽, 왼쪽, 대각선 방향 모두 가능하다. 대각선 방향은 왼쪽 위, 오른쪽 아래, 오른쪽 위, 왼쪽 아래 방향이 모두 가능하다. 연속하는 방향이 중간에 바뀌면 안 된다.

입력

첫째 줄에 길이가 100보다 작거나 같은 단어 S가 주어진다. S는 알파벳 대문자로만 이루어져 있다.

둘째 줄에는 표의 행의 개수 N과 열의 개수 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이다.

셋째 줄부터 N개의 줄에는 표의 각 행에 들어있는 알파벳이 주어진다.

출력

입력으로 주어진 표에 단어 S가 존재하면 1을, 없으면 0을 출력한다.

 

예제 입력 1

ABCD
5 5
ACDBE
ABCED
ACCEE
ACHDF
ACBCE

 

예제 출력 1

1

 

---

처음 봤을때, BFS나 DFS로 풀어야하나? 했지만 단순 탐색 문제인거 같아서 딱히 어려움 없이 구현하였다.

 

내 코드

import sys

# 위, 아래, 왼쪽, 오른쪽, 왼쪽 위 대각선, 오른쪽 위 대각선, 왼쪽 아래 대각선, 오른쪽 아래 대각선
dxs = [-1, 1, 0, 0, -1, -1, 1, 1]
dys = [0, 0, -1, 1, -1, 1, -1, 1]


def in_range(nx,ny):
    return 0<=nx<N and 0<=ny<M

if __name__=="__main__":
    S = str(input())
    N,M=map(int, input().split())
    board = [list(map(str, input())) for _ in range(N)]
    
    visited = [[0]*M for _ in range(N)]
    
    length = len(S)
    for i in range(N):
        for j in range(M):
            if board[i][j] == S[0]:
                is_True=False
                for dx,dy in zip(dxs,dys):
                    cnt=0
                    for l in range(length):
                        ni = i+dx*l
                        nj = j+dy*l
                        if in_range(ni,nj) and board[ni][nj] == S[l]:
                            cnt+=1
                        else:
                            break
                    
                    if cnt == length:
                        print(1)
                        sys.exit()
    
    print(0)

 

방향을 한번 정하고 단어 S 길이만큼 연속되면 찾는거임