Language

풀이과정 해당 문제는 방문 표시만 제대로 하면 쉽게 해결할 수 있는 문제이다. 물론 방문 표시가 생각보다 까다롭다. 😂 시작점에서 끝점까지 도달하는 최단 거리는 너비 우선 탐색(BFS)으로 구현하면 된다. 그렇다면 이 문제의 핵심은 방문 표시이다. 탈출을 하기 위해서는 '.' 공간만 이용할 수 있다. 물론 주어진 n*m 행렬 맵에서는 키라는 특이한 요소를 첨가했다. 키의 종류는 a, b, c, d, e, f 총 6가지이며, 키의 종류 따른 문의 종류도 A, B, C, D, E, F 총 6가지이다. 문제에서는 탈출구까지 가는 길에 문이 있으면 해당 문에 맞는 키 값을 소유하고 있어야 한다. 그렇기 때문에 BFS 탐색할 때 방문 표시를 가지고 있는 키 값들에 따라 해주어야 한다. 키의 종류는 총 6가지이다...

10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이에 도움 되었던 블로그 😊 [알고리즘] Next Permutation NextPermutation 현 순열에서 사전 순(오름차순)으로 다음 순열을 생성합니다. 즉 배열을 가장 작은 값으로 정렬한 뒤, 한 자리씩 swap하면서 출력합니다. 만약 숫자배열이라면 각각의 자리를 합해서 velog.io 문제 풀이 해당 문제는 permutation 알고리즘에 대해 알고 있으면 쉽게 문제를 해결할 수 있다. c++에서는 알고리즘 라이브러리에서 next_permutation을 제공하고 있고, python에서는 itertools에..

23817번: 포항항 첫번째 예제의 경우 오른쪽 3칸, 왼쪽 1칸, 아래쪽 3칸, 오른쪽 1칸, 왼쪽 3칸으로 총 11칸 이동하여 5개의 식당을 방문할 수 있다. 두번째 예제의 경우 장애물에 가로막혀 5개의 식당을 방문할 수 www.acmicpc.net 풀이과정 해당 문제를 해결하려고 많은 시행착오가 있었습니다. 😂 맞왜틀.. python3로는 해결할 수 없는 건가.. 실력이 부족하여 해결하지는 못했지만 혹시 해결하신 분 있으시면 댓글로 달아 주시면 감사하겠습니다. 😊 1. 해당 문제는 dfs, bfs 둘 다 사용하였다. 2. 데이터를 입력받을 때 "S"와 "K"의 좌표를 미리 dist 배열에 튜플 형식으로 입력받았다. 입력받을 때는 "S"에서 시작하기 때문에 dist 배열의 0번째 인덱스로 두었다. 나..

14438번: 수열과 쿼리 17 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을 www.acmicpc.net 풀이 과정 해당 문제는 세그먼트 트리를 알고 있어야 해결할 수 있습니다. 쿼리의 개수가 십만 개인데 배열의 크기마저 최대가 10^9입니다. 해당 문제를 단순하게 인덱스 사이의 min 값으로 출력하게끔 설정하면 0.1초 만에 시간 초과를 보게 될 것입니다. 😶‍🌫️ 그렇다면 세그먼트 트리가 무엇인가? 배열의 "연속적인" 구간 합 또는 구간의 min, max 값을 찾을 때 사용하는 알고리..

17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 해당 문제는 정말 주어진대로 문제를 풀었습니다. 똑같은 곧을 방문한 적이 있으면 출력 값을 1 더해주고 반환해주고, 개미 놈이 이동할 수 있는 경우를 다 설정하여 해당 방향에서 양 갈래 길로 가는 경우로 dfs 탐색을 해주었습니다.. 하지만 python으로는 이렇게 주어진 대로 문제를 해결하면 시간 초과가 발생하네요.. 경우의 수가 1부터 22까지이기 때문에 미해결 코드로 1부터 22까지 출력해서 밑에 코드로 제출했더니 통과가 되었네요.. print(..

23741번: 야바위 게임 첫 번째 줄에 정점 수 $N$, 간선 수 $M$, 게임 시작 시 공이 놓여있는 정점 번호 $X$, 공이 든 컵이 움직인 횟수 $Y$가 주어진다. ($1 \leq N, Y \leq 10^3$, $1 \leq M \leq 10^4$, $1 \leq X \leq N$) 다음 줄부터 $M$ www.acmicpc.net 풀이과정 멍청한 상원이.. 그거 하나 제대로 기억 못 해서 나를 이렇게 힘들게 하다니,, 🤦‍♂️🤦‍♂️ 해당 문제는 DFS로 접근하였습니다. 아마도 BFS로 접근하여도 무리 없이 문제를 해결할 거예요 시작 시 공이 놓여있는 정점 번호(x)부터 시작하여서 연결된 다른 정점으로 이동해서 이동 횟수가 Y인 정점을 저장해주면 됩니다. 하지만 해당 정점으로 이동할 때 정점으로 ..

19641번: 중첩 집합 모델 S번 노드가 루트 노드일 때, 번호가 가장 낮은 노드부터 오름차순으로 방문해서 중첩 집합을 구성했을 때, 각 노드의 번호 left 필드와 right 필드를 출력한다. 총 N개의 줄에 걸쳐 i번째 줄에 i번 www.acmicpc.net 풀이 과정 만약 문제가 잘 이해 안 된다면 표를 잘 보시면 됩니다. 😊 표의 예시에서 "HI-ARC"가 root 노드로 시작됩니다. 그러기 때문에 root 노드 "HI-ARC"의 왼쪽 노드는 order을 1로 가집니다. 그 이후에 "HI-ARC"와 연결된 노드를 찾습니다. 표에서는 "경영 지원실"이 제일 빠른 노드입니다. 해당 "경영 지원실"의 왼쪽 노드는 다음 order인 2를 가집니다. "경영 지원실"과 연결된 노드... 노드... 연결된 ..

t or reversed_front > h : continue if t - reversed_back + reversed_front in visited : continue visited[t-reversed_back+reversed_front] = True q.append([t-reversed_back+reversed_front,depth+1]) else : print(-1)