dfs

백준 1987번: 알파벳(javascript, DFS, 백트래킹)

말이 지날 수 있는 최대의 칸 수를 구하는 문제이다. 최대의 칸을 구해야 하기 때문에 단순 BFS가 아닌 완전탐색 혹은 백트래킹을 이용해 문제를 풀어야 하겠다고 생각했다. 왜냐하면 DFS나 BFS는 한번 방문한 곳은 다시 방문하지 않는데 이 때문에 방문경로에 따라 최대값이 달라지는 경우가 생기기 때문이다. 백트래킹 풀이를 위해서 방문배열을 만들었는데 아스키코드를 이용해 방문을 체크하였다. 왜냐하면 Set자료형에 방문한 알파벳을 넣을수도 있지만 Set은 원소를 집어넣을 때 O(n)이 필요하지만 아스키코드를 이용해 배열의 인덱스에 바로 접근하면 O(1)로 시간복잡도를 줄일 수 있기 때문이다. 그리고 DFS의 인수로 cnt를 주어서 DFS가 재귀할 때마다 cnt에 1을 더해 최대값을 구하고자 했다. 이를 이용..

백준 1325번: 효율적인 해킹(javascript, DFS)

문제는 쉬웠지만 시간관리를 잘해야 하는 문제였다. 문제는 기본적인 문제인데 트리 구조를 만든 후 부모노드를 통해 자식 노드의 개수들을 세는 문제였다. 최대값을 찾아야 하므로 완전탐색을 이용해야 함을 알 수 있었고 N이 10^4로 좀 컸지만 시간제한이 5초로 매우 넉넉하여 쉽게 풀 수 있을것 같았다. 그러나 시간초과가 여러번 났는데 트리를 탐색하는 방법에 문제가 아닌 트리를 배열로 표현하기 위해 배열을 선언하는 과정에서 문제가 있음을 알 수 있었다. 먼저 원래의 배열 선언 코드는 다음과 같다. let tree = new Array(N+1) for(let i=0; i Number(a)) const tree = Array.from({ length: N + 1 }, () => []); for (let i=1; i

프로그래머스: 여행 경로 (파이썬, DFS, 백트래킹)

꽤나 어려운 문제였다. 코드를 짜는 것 자체는 어렵지 않았으나 문제의 엣지케이스를 생각하는데 어려움이 있어 처음에 접근을 잘못한 문제다. 주어진 항공권을 모두 써야 하므로 DFS로 접근을 해야함을 알 수 있다. 이때 가능한 경로가 여러 개일수도 있는데 나는 tickets배열을 lambda식으로 정렬하면 알파벳 순서가 앞서는 경로를 탐색할 것이라 생각했다. 그러나 그렇게 풀면 테스크 케이스1에서 계속 실패했는데 이에 대한 엣지케이스를 생각하는 것이 쉽지 않았다. 특정한 엣지 케이스를 생각하진 못했지만 여러개의 경로를 비교해야 하므로 백트래킹을 이용해 풀어야겠다고 생각했다. 백트래킹은 DFS의 응용으로 분기점에서 다른 경로들또한 탐색하도록 하는 알고리즘이다. 문제에서 여행 경로의 길이는 tickets배열의 ..

프로그래머스: 네트워크 (파이썬, DFS)

비교적 쉬운 난이도의 문제였다. DFS를 통해 그래프를 탐색하는 전형적인 문제였기 때문이다. LV3에서 정답률이 높은 문제가 LV2에서 정답률이 낮은 문제보다 쉬운 것 같다.. 먼저 두 노드간에 간선 유무를 2차원 배열을 통해서 알려주는데 인접 행렬을 이용해서 그래프를 표현한다. 그래프를 표현하는데는 인접 리스트와 인접 행렬이 있는데 난 인접 행렬을 선호하고 그 중에서도 본 문제풀이와 같이 부모, 자식을 각각의 인덱스에 해당하는 리스트에 넣어서 구현하는 방법을 선호한다. 문제풀이 코드는 다음과 같다. def dfs(node, graph, visited): visited[node] = True for child in graph[node]: if not visited[child]: dfs(child, gra..

프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)

N*M 행렬에서 (0,0)에서 (N,M)까지 도달하는 최단경로를 찾아야 하는 문제이다. 최단거리를 구할때는 BFS를 이용하는 것이 좋다. 왜냐하면 DFS는 노드의 끝까지 도달하기에 여러 경로를 비교하기에는 시간복잡도가 크기 때문이다. DFS와 BFS를 구현해본지 오래 되었기에 공부하는 차원에서 두가지 방법 모두로 풀어보려 했다. 먼저 DFS이다. DFS는 분기점에서 트리의 끝까지 탐색하고 돌아오기에 탐색 시간이 길고 deepcopy를 이용해 행렬을 탐색마다 새로 할당해주어야 해서 일반적으로 시간초과가 잘 난다. BFS가 아닌 방법으로 최단경로를 찾으려면 사실 DFS말고 DP를 쓰는게 시간복잡도면에서 좋긴하다. from copy import deepcopy import sys sys.setrecursion..

백준 17070번: 파이프 옮기기 1 (파이썬, DFS, DP)

멘탈이 나간 문제이다. 골드V에서 이정도로 헤멘건 처음이다.. 삼성 A형 기출문제중 하나인데 2차원 배열이 주어지길래 당연히 dfs, bfs로 접근하려 했다. 나는 bfs로 접근하였는데 파이프가 가로인지, 세로인지, 대각선인지 판단을 해야해서 queue에 두 점의 좌표를 튜플과 리스트로 감싸 넣었다. 대각선일땐 세점이 방문 불가하고 파이프의 왼쪽은 파이프가 옮겨질 때 옮겨지기 전 파이프 오른쪽의 좌표로 옮겨진다는 두 포인트를 잡고 코드를 짰다. import sys from collections import deque def bfs(n): global cnt queue = deque(n) while queue: now = queue.popleft() if now[0][0] - now[1][0] == 0: ..

백준 13565번: 침투 (파이썬, DFS)

전류가 통하는 격자는 0, 통하지 않는 격자는 1이다. outder side에서 inner side로 침투하면 성공이므로, 첫번째 행의 원소들에 대해서만 DFS를 하면 된다. 마지막 행에 도달했다는것을 알기 위해 방문을 확인하는 배열을 따로 만들었다. outer side에서만 DFS를 하므로(방문), inner side에 방문을 했다면 침투에 성공한 것이기 때문이다. 여담으로 출력을 Yes로 했다가 계속 틀려서 머리가 터지는 줄 알았는데 대소문자 구별을 잘해야 하고 문제 조건을 꼼꼼히 읽어야 한다.. import sys sys.setrecursionlimit(10**9) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def dfs(x, y): visited[x][y] = True f..

백준 2468번: 안전영역 (파이썬, DFS)

문제 자체는 기본적인 DFS의 구현이였으나 안전한 영역의 최대 개수를 구하기 위해 한번의 과정이 더 필요하였다. 2차원 배열이기 때문에 각 배열의 원소들에 접근하기 위해서는 2중 반복문이 필수이다. 이때 높이는 1이상 100이하 정수이고 N은 100보다 작으므로 3중 반복문이라 하더라도 100^3=10^6, 시간복잡도는 O(N^3)으로 시간초과에 걸리지는 않는다. 따라서 입력되는 배열들 각각에 max함수를 적용후, 그 값들에 다시 max함수를 적용하여 반복문의 최대 range를 정하고 dfs를 적용하면 된다. import sys sys.setrecursionlimit(1000000) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def dfs(x, y): visited[x][y] =..