🧩 Problem Solving
[SWEA] 프로세서 연결하기
date
Aug 28, 2022
slug
swea-processor-connect
author
status
Public
category
🧩 Problem Solving
tags
SWEA
summary
type
Post
thumbnail
문제분석 및 설계
모든 코어에 대하여 가능한 모든 방향으로의 dfs 수행
각 경우에 따라 변경된 map 정보를 전달해야 함(dfs 호출 후 변경 취소 코드 필요)
DFS 가지치기
1) 가장자리에 있는 core 제외
2) 상하좌우 모두 연결 불가능한 core 제외
3) core 저장 시 진행 가능 방향 탐색하여 기록
BFS?!?
- 최소길이 < 라는 표현으로 인해 BFS 라고 생각하기 쉽지만
- 코어를 최대한 많이 가져가야 하므로 BFS가 아니라 DFS 로 풀어야 함
백트래킹
- 배열채우기 - DFS 호출 - 배열 복구
실패
00000
01110
01110
01110
00000
에서 (2,2) 에 있는 코어를 만날 때 dfs 가 더이상 가지 않고 종료됨 ⇒ dfs 종료가 아니라 다음 코어로 넘어가야 함
성공
입력 받을 때 모든 방향으로 가지 못하는 코어 1차로 제외
현재 맵 기준 더이상 갈 수 있는 방향이 없는 코어에 대해 아무것도 하지 않고 그냥 다음 코어로 넘어가는 dfs 시행
- 추가) 해당 코어에서 갈 수 있는 방향이 있더라도 아무 전선도 연결하지 않는 경우가 더 나을 수도 있음!!! 따라서 모든 코어에 대하여 그냥 다음 코어로 넘어가는 DFS 호출할 것
DFS 설계 시 주의
- dfs 시행 시 더이상 갈 수 있는 경우가 없는 노드에 대하여 → 여기서 dfs 그만두지 말고 다음 노드로 넘어갈 수 있도록 해야 함!!!!! 해당 노드에서 더이상 갈 수 있는 방향이 없다면 dfs 종료조건이 아니고 아무것도 안 하고 다음 노드로 넘어가는 조건임을 기억할 것
- 하나의 dfs 호출 후, 해당 호출로 인하여 변경된 데이터 다시 초기화 필요한 경우 고려할 것