BFS

이 문제를 보면서 어떻게 풀어야 할지 고민하다가 알고리즘 분류를 보고 더 많이 헷갈렸다. 원래 문제를 풀 때 알고리즘 분류를 잘 보지 않으려고 하는데 이문제는 접근 자체가 너무 고민되어 보고 말았다.... 알고리즘 분류에 플로이드-와샬이 적혀있었는데 나는 기본적으로 플로이드-와샬 알고리즘도 다익스트라처럼 가중치가 있는 그래프의 최단경로가 있을 때 사용할 거라 생각했었는데 이 문제는 가중치가 없어서 어떻게 플로이드 와샬로 풀지 와닿지 않았다. 그래도 일단 플로이드-와샬 알고리즘의 기본 틀은 알고 있었기 때문에 그 틀에 맞추어 풀어보았다. 나의 아이디어는 아래와같다. 1. 2차원 배열에는 현재 행을 기준으로 열이 행보다 작으면 True (1)을 준다. 2. 플로이드-와샬알고리즘을 활용하여 비교대상 값(s)이..

오랜만에 백준을 풀었고, 오랜만에 시간 초과 늪에 빠졌다. 최대한 시간을 줄여 파이썬까지 통과해보고 싶었지만 아직 내실력에서는 Pypy통과가 최선이었다. 문제를 간략히 설명하자면, 존이 N개의 동영상 중 N-1개의 동영상 쌍을 만들어서 유사도를 구해놓았다. 동영상 쌍을 만들 때 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 만들었을 때, Q개의 질문(v번의 동영상과 유사도가 k이상인 동영상의 개수)의 답을 구하는 문제이다. 문제에서 가장 큰 힌트부분은 한 동영상에서 한 동영상으로 가는 경로가 반드시 하나인 점. 즉, 방향이 존재하지 않고 사이클이 없는 그래프인 트리구조로 만들 수 있다는 점이다. 나는 위 점에서 힌트를 얻어 딕셔너리를 활용하여 트리를 만들었고, 이를 이용한 BFS탐색..

SWEA D4문제를 추천순으로 풀고 있는데 어제오늘은 좀 쉬운 문제를 풀게 됐다. (사실 요즘 바빠서 알고리즘 풀 수 있을까? 했는데 다행이다.) 이 문제는 제목이 길찾기이지만, 사실 미로 찾기, 그래프 탐색하라는 문제이다. 제한시간도 30초이고 최대 방문지 점도 100개이기 때문에 BFS로 풀지, DFS 풀지 고민 없이 풀고 싶은 방식으로 풀어도 해결할 수 있을 것이다. 나는 처음보자마자 BFS가 떠올랐기 때문에, BFS로 풀어보았다. 우선 100개의 방문 체크를 할 리스트를 만들고 인접 행렬을 만들었다. 이 문제는 "출발 도착 출발 도착 출발 도착..." 이런식으로 Input값을 주기 때문에 한 번에 다 받은 다음에 두 개씩 끊어서 인접 행렬에 넣어 줄 필요가 있었다. 변수를 받고 도착지(99)에 도..

최근에 풀었던 문제 중에 가장 재밌게 푼 문제인 것 같다. 물론 쉽게 푼 문제는 아니었지만, 어떻게 풀지 고민하는 과정과 실제로 그 과정에서 정답이 나오는 게 알고리즘 문제를 푸는 재미인 것 같다. 문제를 간단히 설명하자면, 몇 번의 클릭으로 지뢰가 아닌 곳을 오픈할 수 있는지 횟수에 대한 최솟값을 묻는 문제이다. 추가적인 제약사항은 *(지뢰가 아닌 곳)을 클릭했을 때, 인접한 곳에 지뢰가 없다면 인접한 블록까지 공개가 된다. 그림에서 숫자는 인접한 위치의 지뢰 개수인데, 문제에서 묻는 것은 최소 클릭 횟수이기 때문에 구현하지 않았다. 문제를 처음 보고 최소한의 횟수? 'DFS!'를 생각했지만, 게임판의 길이(N) 이 300까지 가능하기 때문에 DFS는 절대 아니라고 생각했다. 그럼 내 지식에서 남은 보..