문제 https://www.acmicpc.net/problem/1327 1327번: 소트 게임 홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집 www.acmicpc.net 풀이과정 💡 아이디어 순회는 언제 끝날까? ✅ 주어진 숫자들을 순서대로 정렬한 answer 를 구한다. ✅ 문제의 조건대로 정렬을 반복하다가 answer와 일치하는 순간 정렬 횟수를 반환 ⏩️ 최소 횟수이므로 BFS가 적합 그렇다면 방문처리는 어떻게 해야 할까? ✅ N의 최댓값이 8이므로 숫자 인덱스로 배열 방문처리를 한다면 visited[88888888] 필요 ✅ 객체를 활용하면 메모리를 ..
문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 자바스크립트(node.js)로 풀이했습니다. 풀이과정 1차 시도 실패 이유 - 메모리 초과 갈 수 있는 모든 땅에 대해 bfs()를 다 돌림 -> visited는 bfs()를 호출할때마다 계속해서 할당 -> 메모리 초과 이뿐만 아니라 최단거리는 직전 땅의 거리 정보를 이용해 구할 수 있으므로 각 땅이 아니라 전체를 bfs() 돌리는게 맞다 for ..
1️⃣ 매개변수로는 그래프와 시작점 받기 def bfs(graph, start): 2️⃣ deque() 활용하여 queue 생성 queue = deque() 3️⃣ 시작점 방문하고 큐에 시작 인덱스 추가 visited[start] = True queue.append(start) 4️⃣ queue가 빌때까지 반복 큐에서 가장 먼저 들어갔던 인덱스 꺼내서, 해당 인덱스와 연결된 노드 순회 while queue: cur = queue.popleft() for node in graph[cur]: 5️⃣ 만약 노드를 방문하지 않았다면, 방문하고 큐에 해당 노드 인덱스 추가 if not visited[node]: visited[node] = True queue.append(node)
