반응형
1. 문제 소개
- 그래프 탐색 문제이다
- 깊이, 너비 우선 탐색으로만 구현해도 통과가 가능해보인다.
https://www.acmicpc.net/problem/13565
2.코드
def myDFS(N,M,caseMap):
stack = []
visited = []
success = False
for i in range (0,N):
visited.append([False for i in range(M)])
#set start pos
for i in range(0,M):
stack.append((0,i))
while(len(stack) >0):
loc = stack.pop()
row = loc[0]
col = loc[1]
#out of index case
if row < 0 or col < 0 or row >= N or col >= M or visited[row][col]:
continue
visited[row][col]=True
#Block case
if caseMap[row][col] == 1:
continue
print("current row : {} col : {} val : {}".format(row,col,caseMap[row][col]))
stack.append((row,col-1))
stack.append((row,col+1))
stack.append((row-1,col))
stack.append((row+1,col))
#reach to Out line
if (row+1) == N:
success = True
return success
def inputCase():
NM= input().split(" ")
N,M=int(NM[0]),int(NM[1])
caseMap = []
for i in range (0,N):
inline = input()
flatten = [int(x) for x in inline]
caseMap.append(flatten)
return N,M,caseMap
def solution():
N,M,caseMap = inputCase()
rs=myDFS(N,M,caseMap)
if rs ==True:
print("YES")
else:
print("NO")
#print(caseMap)
solution()
3.코멘트
- DFS, BFS는 할 때마다 자꾸 까먹는다.
- 비슷한 문제 유형을 계속 풀어봐야 할 것 같다
반응형
'Algorithm' 카테고리의 다른 글
Baekjoon 백준 알고리즘 - 스위치 켜고 끄기 ( 1244 ) (0) | 2021.10.17 |
---|---|
Baekjoon 백준 알고리즘 - 되돌리기 ( 1360 ) (0) | 2021.07.26 |
Baekjoon 백준 알고리즘 - 경로찾기 ( 11403 ) (0) | 2021.06.07 |
Baekjoon 백준 알고리즘 - 서버실 ( 17245 ) (0) | 2021.05.31 |
Baekjoon 백준 알고리즘 - 체인 ( 2785 ) (0) | 2021.05.30 |