Problem Solving/백준
[15705] 단어 찾기
충무로술겜마
2021. 7. 28. 00:03
https://www.acmicpc.net/problem/15705
15705번: 단어 찾기
N×M 크기의 표의 각 칸에 알파벳 대문자가 하나씩 쓰여 있다. 단어 S가 주어졌을 때, 표에 단어 S가 있는지 없는지 구하는 프로그램을 작성하시오. 단어 S가 표에 존재하려면, 표의 한 칸에서 시작
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
# 세로 확인
def doesRowHaveSubstring():
for i in range(n):
for j in range(m):
a = int(i)
b = int(j)
temp = ''
while a < n and b < m:
temp += (chart[a][b])
a += 1
if (s in temp) or (s[::-1] in temp):
return True
temp = ''
return False
# 가로 확인
def doesColHaveSubstring():
for i in range(n):
for j in range(m):
a = int(i)
b = int(j)
temp = ''
while a < n and b < m:
temp += (chart[a][b])
b += 1
if (s in temp) or (s[::-1] in temp):
return True
temp = ''
return False
# 우대각선 확인
def doesRightDiagonalHaveSubstring():
for i in range(n):
for j in range(m):
a = int(i)
b = int(j)
temp = ''
while a < n and b < m:
temp += (chart[a][b])
a += 1
b += 1
if (s in temp) or (s[::-1] in temp):
return True
temp = ''
return False
# 좌대각선 확인
def doesLeftDiagonalHaveSubstring():
for i in range(n):
for j in range(m):
a = int(i)
b = int(j)
temp = ''
while a > -1 and b > -1:
try:
temp += (chart[a][b])
except IndexError:
pass
a += 1
b -= 1
if (s in temp) or (s[::-1] in temp):
return True
temp = ''
return False
s = input()
n, m = map(int, input().split())
chart = [list(input()) for _ in range(m)]
if doesRightDiagonalHaveSubstring():
print(1)
elif doesLeftDiagonalHaveSubstring():
print(1)
elif doesRowHaveSubstring():
print(1)
elif doesColHaveSubstring():
print(1)
else:
print(0)
|
cs |
딱 봐도 브루트포스 substring 문제입니다.
근데 이제 대각선만 조심하시면 쉬운 문제네요. (좌 대각선 깜빡하고 삽질함)