개발자 되기(feat.SSAFY)

1. 사용한 알고리즘 | 자료 구조 BFS 큐 2. 풀이 접근 방식 전형적인 BFS 문제입니다. K회 만큼 BFS 연산 후 Queue 에 있는 값을 정렬, 출력합니다. 3. 특이사항 Stack 2개를 스왑하는 방식으로 사용하여 deque 를 import 하지 않고 BFS 알고리즘을 구현할 수 있습니다. 4. 언어 | 실행시간 | 메모리 사용량 Python3 | 1264ms | 97164kb from sys import stdin def solution(): # 1. 입력 # N: 정점의 수 | M: 간선의 수 # K: BFS 연산 횟수 | X: BFS 연산 시작점 N, M, K, X = map(int, stdin.readline().split()) # 2. 선언 # 2-1. paths: 간선 정보 pat..

사용한 알고리즘 / 자료구조 우선순위 큐 (heapq) 트리 다익스트라 알고리즘 접근한 방식 두 로봇 사이의 최단 거리를 계산해야 합니다. 일반적인 다익스트라 방식으로 접근했습니다. 단, 현재 사용한 경로에서 '가장 긴 경로'를 제외해야 하므로 두 로봇 사이의 최단 경로 정보를 저장해야 합니다. 배열을 사용해 이를 구현합니다. path: 접근 경로를 저장하는 리스트. index == 노드 번호, value == 출발지 path_distance: 경로의 길이를 저장하는 리스트. index == 노드 번호, value == 경로의 길이. 다익스트라 연산을 끝마친 후 경로를 역추적합니다. 로봇1에서 로봇2까지의 거리를 계산한 뒤 , 가장 길었던 경로(worst_path)를 거리에서 제합니다. 어려웠던 점 다익..

사용한 알고리즘 및 자료구조 BFS 큐 델타를 이용한 2차원 좌표 탐색 접근 방식 로봇이 한 턴 내에 할 수 있는 동작은 세 가지다. 1~3칸 전진. 좌로 회전. 우로 회전. 로봇의 상태를 que에서 받은 뒤, 위 세 가지 연산을 전부 처리한다. 로봇의 위치와 로봇이 바라보는 방향 모두를 정확히 기록해야 하기에, 3차원 방문 여부 리스트를 활용했다. 문제 특이사항 일반적으로 2차원 좌표 탐색 문제에서, '방향을 돌리는' 연산은 나머지 연산을 통해 쉽게 구현할 수 있다. (나누기를 활용해 2차원 좌표 탐색에 활용하는 문제 샘플을 곧 업로드 하겠습니다.) 하지만 이 문제는 '동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4' 라고 명시하고 있다. 따라서 좌표를 입력받을 때 적당히 변형하거나, 회전하는 함수를 ..

2468. 안전영역 사용한 알고리즘, 자료구조 및 기법 BFS, 큐 델타를 이용한 2차원 배열 완전탐색 접근 방식 1. BFS로 순회. '수위'와 '건물의 높이'를 각 수행마다 비교하며 '구역'의 넓이를 구해야 한다. 2. 수위: 가장 낮은 건물의 높이보다 1 낮을 때~ 가장 높은 건물의 높이와 같을 때까지 모든 경우의 수를 완전탐색. 문제 특이사항 탐색 시작 / 끝 조건 설정이 헷갈릴 수 있다. 어려웠던 점 1. 종료조건의 설정: 높이가 올라갈수록 '구역'의 갯수가 수위에 따라 지속적으로 증가하다가 감소한다고 생각해서 아래와 같은 전제를 짜고 풀었다가 오답 처리당했다. 종료조건: 모두 물에 잠기거나 높이가 상승했을 때 '구역'의 갯수가 이전보다 줄었을 때. 느낀 점 좀 더 범용성 있는 방식으로 구현한 ..

1260. DFS와 BFS 사용한 알고리즘 및 자료구조 1. BFS, 스택 2. DFS, 큐 3. 연결 리스트 접근 방식 1. BFS와 DFS 를 구현한다. 문제 특이사항 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 한다. 스택: 후입선출 큐: 선입선출 의 특징을 염두에 두고 구현해야 한다. 2. DFS 특정 지점의 연결 리스트를 조회할 때 연결 리스트를 1) 오름차순 정렬 후 2) pop()으로 스택에 삽입하면 3) 정점 번호가 큰 순서대로 스택에 삽입된다. ==> 정점 번호가 작은 순서대로 조회할 수 있다! 3. BFS 특정 지점의 연결 리스트를 조회할 때 연결 리스트를 1) 내림차순 정렬 후 2) pop() 으로 큐에 삽입하면 3) 정점 번호가 작은 순서대로..

사용한 알고리즘 BFS 접근했던 법 시작점에서 끝 점까지 가는 방법을 출력해야 한다. `True` 와 `False` 로 방문 여부만을 판단하는 일반적인 `visited`리스트를 사용하는 대신 visited = [''] * 10000 를 선언. vstd에 '루트'들을 입력하며 방문처리와 루트 보관을 동시에 한다. vstd[st] 에 아무 값(',')을 채워넣고 BFS 연산 시작. vstd[ed] 가 None이 아닐 때 == 한 번이라도 닿았을 때 vstd[ed]를 출력하고 BFS 종료. 단, vstd[st]에서 임의의 값을 넣고 시작했으므로 적당한 슬라이싱이 필요. 어려웠던 점 '시작점에 방문 처리 안 해도 적당히 잘 풀리겠지' 하다가 틀렸다. 슬라이싱으로 오답을 받았다. D, S, L, R을 최소한의 연..