Stargazer

접근: 대충 봐도 탐색 문제이고, 맵 전체를 탐색 해야 하기 때문에 BFS로 탐색하기로 결정함 전략: 우선 시작점은 (0,0)으로 하고, 건물 외벽부터 시작이므로 맵의 변을 2씩 증가시켜서, 패딩을 주어 갈수 있는 경로를 만들면 뚫려있는 곳이나 열쇠를 가지고 있는 문은 통과가 가능하다. 그 다음 주어진 키에 맞게 먼저 전체 탐색을 BFS로 진행하고, 그 중에 발견된 키(중복 포함)가 있으면, 다시 한번 전체 탐색을 한다. 더 이상 새로운 키가 발견되지 않을 때까지 반복해서 전체 탐색을 진행 한다. 그 과정에서 발견된 문서는 합계하여 출력한다. 코드: #include #include using namespace std; int test; char map[102][102]; bool visit[102][10..

접근: 처음에는 어떻게 접근 해야 할지 직접 그려보면서, 관계를 파악해보았다. 대충 봐도 그래프 이론으로 풀어야 하는데, 그 중 순서 정렬이 필요하기 때문에 위상 정렬로 풀어야 한다는 걸 알 수 있다. 전략: 대소 관계를 표현하기 위해 입력을 digraph(유향그래프) 형태로 입력을 받는다.(형식은 자유 - 행렬, 인접리스트) 진입 차수가 0인 노드부터 큐에 넣고, 큐에서 하나씩 제거하면서 출력한다. 제거한 노드가 가리키는 다른 노드의 진입 차수를 한개 줄이고, 만약 0이라면 큐에 삽입한다. 코드: #include #include #include using namespace std; int n,m; vector comp; vector income; int main(){ cin >> n >> m; comp..