궤도

문제 풀이 이런 그래프가 있다고 하자. 이 그래프를 탐색할 시 선택의 순간이 2번 있다. 바로 1번 정점과 2번 정점에서이다. 1번 정점에선 2번 또는 3번 정점으로 갈 수 있다. 2->3의 순서로 큐에 넣어도 되고 3->2의 순서로 큐에 넣어도 된다. 2번 정점에선 마찬가지로 4->5 또는 5->4의 순서로 큐에 넣을 수 있다. 이 순서는 순전히 처음에 그래프의 연결된 정점을 어떤 순서로 저장했느냐에 따라 달라진다. 1->2, 3으로 저장했다면 2->3의 순서로 큐에 들어갈 것이고 1->3, 2로 저장했다면 3->2의 순서로 큐에 들어갈 것이다. 입력된 방문 순서에 따라 정점의 저장 순서를 바꿀 것이다. 먼저 인접 정점의 정보를 이렇게 저장했었다고 가정하자. 1->2, 3 2->1, 4, 5 3->1,..

문제 풀이 굉장히 비효율적인 방법으로 풀었는데 시간초과가 나지 않았다. 문제를 풀고나서 효율적으로 작성한 코드를 몇개 봤지만 도통 이해가 되지 않아서...강해져서 돌아와야겠다. 아무튼 내가 한 비효율적인 방법은 정점의 개수만큼 dfs를 실행한 것이다. 최대 입력이 3,000이라 시간초과가 발생할 것이라고 생각했는데 그렇지 않았다. 사실 다른 효율적인 방법을 나름 시도해봤지만 영 제대로 풀리지가 않았다. myunji.tistory.com/350 [백준] 4803번 : 트리 문제 풀이 트리의 가장 큰 특징은 사이클이 없단 것이다. 이러면 안된다는 뜻이다. 그래서 이번에 새로 방문할 정점이 이전에 방문한 정점인지, 그래서 사이클이 형성됐는지 확인해야 한다. 근 myunji.tistory.com 이 문제에서 그..

문제 풀이 이 문제를 풀고나서 다른 사람들의 소스코드를 몇 개 봤다. 근데 다들 큐를 2개 사용하거나, while문을 두번 돌리거나 하는 식으로 홍수의 확산과 고슴도치의 이동을 따로따로 관리하는 방법으로 코드를 작성하는 듯 했다. 근데 굳이 그럴 필요 없다. 고슴도치가 없어서 내가 좋아하는 호랑이로 대체했다. 아무튼 이렇게 홍수와 고슴도치의 초기 상태가 주어졌다고 하자. 큐에 홍수의 위치 정보를 먼저 넣고 고슴도치의 위치 정보를 넣었다. 큐의 맨 앞에 있는 파도가 빠지고 새로운 파도의 위치 정보가 큐에 삽입된다. 이런식으로 하면 큐 하나로 홍수와 고슴도치를 관리할 수 있다. 한편, 이렇게 이전에 고슴도치가 방문한 곳이 홍수에 잠길 수도 있다. 그렇기 때문에 고슴도치의 visited는 다른 배열에 저장해서..

문제 풀이 이 문제의 목적은 최단경로를 찾는게 아니라 최소파괴경로를 찾는 것이다. 그니까 아무리 돌아가는 길이라고 해도 벽을 덜 부수는 경로를 우선으로 해야한다. myunji.tistory.com/289 [백준] 2206번 : 벽 부수고 이동하기 문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신 myunji.tistory.com 이 문제랑 헷갈리면 안된다. 아무튼 벽을 안부수는 길을 우선시 해야 한다는 가중치 조건이 생겼지만, 벽을 부순다 or 안부순다 2가지 경우만 있으므로 덱을 사용한 0-1 너비 우선 탐색을 할 수 있다. 길로 갈 때는 덱의 앞에 삽입하고, ..

문제 풀이 myunji.tistory.com/287?category=1154147 [백준] 1697번 : 숨바꼭질 문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아 myunji.tistory.com 이 문제의 응용버전이다. 순간이동과 앞뒤 이동 모두 1초가 걸렸던 1697번과 달리 이번엔 순간이동을 0초만에 할 수 있다. 즉 각 이동에 대한 가중치가 달라진 것인데, 그래프의 관점에서 말하자면 간선에 가중치가 생긴 것이다. 이런 경우에서 최단거리를 찾고자 한다면 가중치가 작은 것을 우선으로 탐색해야 한다. 괜히 가중치 0으로 갈 수 있는 곳을 가중치 ..

문제 풀이 클립보드를 관리하는 것이 중요한 문제다. 처음에는 덮어씌워진다길래 변수 하나로 클립보드를 관리하려 했는데, bfs의 상태에 따라 클립보드의 상태가 다를 수도 있다는걸 생각하지 못한 것이다... 그래서 방문여부를 관리하는 visited 배열을 2차원 배열로 만들어 클립보드의 정보를 저장했다. 그리고 이모티콘의 현상태 정보또한 구조체로 관리했다. 구조체에는 이모티콘의 개수와 그때까지 걸린 시간, 그리고 그 상태에 클립보드에 복사된 이모티콘의 개수를 저장했다. 소스코드 #include #include using namespace std; const int MAX = 1001; struct emoji { int num, time, pasted; }; int S; bool visited[MAX][MAX..

문제 풀이 이 문제는 그냥 구글에 이분그래프라고 검색하고 나온 이미지를 보는 것만으로도 한 절반정도는 풀리는 문제이다. 위키백과 이미지를 가져왔다. 그래프의 정점을 빨간색과 초록색으로 칠한 것을 볼 수 있을 것이다. 이분그래프는 인접한 두 정점을 다른색으로 칠한다고 가정할 때 오직 두가지의 색을 사용해서 모든 정점을 칠할 수 있는 그래프이다. 자료구조때 배웠던가...컴퓨터 알고리즘때 배웠던가...암튼 배웠었다. 아이디어는 간단한 이 문제가 정답 비율 20%대인 이유는 간과하기 쉬운 조건 하나와 메모리 초과 그리고 입력 초기화 떄문 아닐까싶다. 먼저 간과하기 쉬운 조건하나를 말해보도록 하겠다. 바로 모든 정점이 연결됐을거란 보장이 없다는 것이다. 이 그림처럼 다른 정점과 연결되지 않은 정점이 있을 수 있다..

문제 풀이 myunji.tistory.com/284 [백준] 2178번 : 미로 탐색 문제 풀이 이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다. 빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까? 시작점에서 바 myunji.tistory.com 이 문제랑 똑같은 유형인데 그냥 방향이 4개에서 8개가 됐을 뿐이다. 소스코드 #include #include #include #include using namespace std; int matrix[300][300], l; pair dir[8] = {{1, -2}, //나이트가 갈 수 있는 방향 {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -..