궤도

문제 풀이 최소 동작 횟수라고 했으니까 BFS로 풀면 될 것이고, 가로로 놓는 경우와 세로로 놓는 경우의 visited를 따로 처리해야하니까 3차원 배열로 visited를 처리해야겠다. 그리고 3개를 다 들고 돌아다니는건 좀 비효율적이니까...가운데에 있는 통나무 하나만 들고다니려고 한다. 왜 굳이 가운데를 쓰냐면 그게 회전할 때 편하기 때문이다. 통나무의 상태, 그리고 하려는 동작에 따라 체크해야하는 범위가 다르다. 가로 통나무를 UDLR 하면 1x3의 범위를 확인해야 하고, 세로 통나무를 UDLF 하면 3x1의 범위를 확인해야 하고, T하면 3x3의 범위를 확인해야 한다. 이걸 하나하나 따로 처리하는건 비효율적이니까 함수로 만들어서 관리하려고 한다. 소스코드 #include #include #incl..

문제 풀이 그냥 평범한 bfs로 풀 수 있을 것 같은데 생각을 하나 해야한다. 예제 입력 1을 보면 알 수 있듯이 이미 방문한 정점이지만 f 열쇠를 획득한 이후엔 다시 방문할 수 있다. 열쇠 보유 '상태'가 달라졌기 때문이다. https://myunji.tistory.com/289 [백준] 2206번 : 벽 부수고 이동하기 문제 풀이 너어무 어려웠다. 골드 4길래 풀만할 줄 알았는데 아니었다. 반례가 너무 많았어서 기억도 안나고 여기서 더 최적화 할 수 있을 것 같은데 더 이상 못하겠다. 솔직히 설명도 잘할 자신 myunji.tistory.com 이 문제랑 비슷한 개념인데, 참고로 저 문제 이제 완벽하게 이해해서 관련 문제도 2차원 배열 내에서 다 해결했다. 뿌듯 아무튼 저 문제에서의 상태는 '벽을 부순..

문제 풀이 각 턴마다 해야하는 일을 순서대로 써보자. 1. 궁수가 적을 타겟팅 2. 동시에 공격 3. 적 이동 둘 이상의 궁수가 하나의 적을 공격할 수 있다고 하니 타겟팅만 해두고 한번에 공격해야 한다. 궁수의 공격 범위는 반지름이 d인 반원의 형태라고 볼 수 있는데, 그래서 좌, 상, 우의 순서로 탐색하다 제일 먼저 찾은 적을 공격하면 된다. https://myunji.tistory.com/378 [백준] 16236번 : 아기 상어 문제 풀이 계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다. 다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다. 상어가 물고기를 먹는 우선순 myunji.tistory.com 가능한 모든 후보를 찾고 정렬했던 이 문제보단..

문제 풀이 계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다. 다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다. 상어가 물고기를 먹는 우선순위 때문에 좀 헤맸다. 처음엔 단순히 '상-좌-우-하'의 순서로 탐색하면 되겠거니 했는데 '예제 입력 4'에서 틀린 답이 나왔다. 그래서 최단 경로에 위치한 모든 물고기들을 찾은 뒤, 그 물고기들 중에서 가장 우선순위가 높은 물고기를 찾는 방법으로 코드를 다시 작성했다. 소스코드 #include #include #include #include #include using namespace std; vector board; int shark_size = 2; //상어의 크기 int fish_cnt, result; //..

문제 풀이 문제 자체는 그냥 간단한 BFS였는데 그 과정이 너무 더럽다고 해야하나 짜증나게 한다고 해야하나 암튼 그랬다. D, S까지는 그렇다고 치고 L, R을 구현하는게 문제인데, 제일 먼저 생각난건 string이라 그걸로 했더니 tle가 났다. 그러다가 잘 생각해보니 이거 그냥 수학으로 되는 연산이었다...이것만 빨리 알아챘어도.. 소스코드 #include #include #include #include #include using namespace std; string bfs(int source, int target) { vector visited; visited.assign(10000, false); queue q; visited[source] = true; q.push(make_pair(sourc..

문제 풀이 루트노드를 직접 찾아야 한다는 것을 몰라서 많이 헤맸다. 그것만 아니었어도 30분은 아꼈을텐데... 이 문제를 보자마자 제일 먼저 한 생각은 레벨 순회를 해야겠다는 것이었다. dfs에 속한다고 볼 수 있는 preorder, inorder, postorder와 달리 level traversal은 bfs에 속한다. 아무튼 이걸 사용해서 각 레벨별 정점을 정리해야겠다고 생각했다. level1 - 1 level2 - 2, 3 level3 - 4, 5, 6, 7 이런식으로 저장될테니 나중에 레벨마다의 너비를 구할때도 각 레벨의 첫번째 값과 마지막 값의 길이만 구하면 된다. 근데 문제는 각 정점의 열을 구하는 것이었다... 처음에는 분할정복으로 각 정점의 열을 구했는데 이것도 문제는 없는 코드였다. 굳이..

문제 풀이 myunji.tistory.com/287 [백준] 1697번 : 숨바꼭질 문제 풀이 얼핏보면 동적계획법 문제라고 생각할 수도 있다. 하지만 수빈이가 계속 앞으로만 이동하는게 아니라 뒤로도 이동할 수 있어서 bfs로 푸는게 훨씬 쉽다. 현재 지점(X)의 X-1, X+1, 2X가 아 myunji.tistory.com 이 문제에서 지나온 경로를 추가하는 코드만 추가하면 된다. bfs를 통해 거리를 갱신하면서 직전 위치도 함께 저장한다. 그리고 도착점부터 시작점까지 거슬러 올라가며 스택에 쌓고 출력하면 된다. 소스코드 #include #include #include #include using namespace std; const int MAX = 100000; pair pos[MAX + 1]; que..

문제 풀이 일단 다른 섬끼리 다리를 이어야 하기 때문에 각각의 섬을 구분해야 한다. 이런식으로 말이다. myunji.tistory.com/280 [백준] 2667번 : 단지번호붙이기 문제 풀이 문제 이름에 왜 띄어쓰기가 없을까? 그냥 의문점이다. 배열을 돌면서 1로 표시된 지점을 찾으면 그 지점을 root로 하는 bfs 또는 dfs로 연결된 모든 1을 찾는다. bfs, dfs에서 빠져나왔다는 myunji.tistory.com 이 문제에서처럼 dfs를 사용해 각 섬을 구분지을 것이다. 그리고 가장자리에 위치한 모든 땅들에 대해 bfs로 최단거리를 구하는데 만약 이전의 bfs로 구해놓은 최단거리가 4 였다면 거리가 4보다 커질 때 bfs 탐색을 종료해 시간을 아낀다. 소스코드 #include #include..