[SWEA] 정사각형 방

date

Aug 9, 2022

slug

swea-square-room

author

status

Public

category

🧩 Problem Solving

tags

SWEA

summary

type

Post

thumbnail

문제 분석 및 설계

현재 위치에서 갈 수 있는 가장 긴 DFS 깊이 찾는 문제 ⇒ DFS

• DFS 설계 방법
• 스택 사용
• 재귀 호출
• 2차원 배열 탐색 + 각 원소에서 while 통한 dfs 수행 (✔)

DFS 레벨 기억 ⇒ DP

• cache[] : 각 원소에서 시작했을 때 갈 수 있는 최대 길이를 저장해두는 배열(DP)

• 만약 다음 방을 방문한 적이 있다면
• 나의 길이 = 나의 다음 방 길이 + 1

• 방문한 적 없다면
• 갈 수 있을 때까지 간 후(deque 이용)
• 나의 길이 = 나의 다음 방 길이 + 1

가장 긴 방 찾기

• cache[] 배열 탐색해서 가장 길이가 긴 방 찾기

시뮬레이션