1주차 문제 [DFS/BFS]

[ 1. 음료수 얼려먹기 ]

강의 자료에서 재귀로 너무 간단하게 풀어버려서 Stack으로 풀기 도전

코테 TIP

arr(mxn) 행렬에서
n = len(arr) m = len(arr[0])

행렬 초기화 ( 내부 리스트에서 ⇒ 외부 괄호 순 )
visited = [[False] * m for _ in range(n)]

잘못 접근했던 부분들

• 연산자 우선 순위 문제 (‘|’ 와 ‘or’)

if (0 > (x+dx) | (x+dx) > n-1) | (0 > (y+dy) | (y+dy) > m-1):
⇒ 비트 연산자 |, &, ^는 우선순위가 높아 (0 > ( (x+dx) | (x+dx) )) > n-1 이 꼴로 연산해버림

if (0 > (x+dx) or (x+dx) > n-1) or (0 > (y+dy) or (y+dy) > m-1):

⇒ python 코테에서 연산자는 반드시 “OR”, “AND”, “NOT”으로!!!

• 스택 카운팅 (chk의 위치)


실수 : pop이후 먼저 1이면 stack에서 방문 처리하고 넘기기 방식


⇒ 결국 1이 아닌 모든 0의 위치에서 카운팅 = 기본적으로 탐색 알고리즘에서 방문했더라도, 시작점 데이터는 스택에 들어감 = 오류

 


쉽게 해결 : 스택 들어가기도 전에 그냥 밖에서 처리 하고 스택에는 시작점이 0인값만!

⇒ visited에 1인 값은 false로 바뀌지 않음!