알고리즘/BOJ 썸네일형 리스트형 1967번 1967번 - 트리의 지름 1167 이랑 똑같은 문제이다. 1167번은 입력에서 그래프의 양쪽이 연결되어서 주어졌는데, 1967번 같은 경우는 한쪽 방향의 연결만 주어지므로 , 그것만 바꾸면 정답이 된다. 참, 그리고 N의 범위도 더 줄어들었다. DFS, BFS 모두 사용해서 풀 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798#include#include#include#include#includeusing na.. 더보기 1167번 1167번 - 트리의 지름 트리의 지름에 대한 개념이 하나도 없이 문제를 풀었다. 모든 노드에 대해서 DFS를 통해 최대값을 구하는 완전탐색 방식으로 접근했다. 근데 역시나 노드의 최대값이 100000이라는 한계를 뚫지 못하고 시간 초과로 나왔다. 사실 풀때도 이미 이거 시간이 너무 오래 걸리겠는데? 라는 생각을 했지만... 그래서 DP로 가능할까 했더니 DP로 불가능해 보였고, 시간을 줄이기 위해서 leaf node , 즉 연결된 노드가 1개 밖에 없는 노드만을 돌려도 보았다. (2개 이상의 노드에서 dfs를 수행할 경우, 그 길이는 구한 최대값에서 다른 노드로 가는 가중치를 더하면 되므로, 최대값이 될 수 없기에) 하지만 아무리 용을 써도 시간초과는 벗어날 수 없었다. 그래서 트리의 지름의 길이를 알.. 더보기 11725번 11725번 - 트리의 부모 찾기 그래프가 주어지고 , 결국 트리의 노드를 1로 하라고 했기 때문에 DFS나 BFS를 이용하여 탐색하면서 부모 노드의 값만 저장해주면 될 것 같다. 발생한 문제점 cout 더보기 1991번 1991번 - 트리 순회 풀면서 좀 헷갈렸다....... 그리고 입력이 뭐 3개면 A,B,C 이렇게 다 들어오긴 하지만 그게 순서로 들어오는게 아니라 B,C,A 이런식으로 들어올 수도 있다는 점을 간과해서 풀다가 오류가 발생했었다. 내가 푼 방식이 조금 이상하고 그럴 수도 있지만... 아무튼 나는 최대 N이 26으로 작은 값이므로 배열을 생성했고, 알파벳을 숫자로 변환해서 배열의 인덱스로 사용하였다. 전위 순회은 dfs1() 함수로 중위 순회은 dfs2() 함수로 후위 순회은 dfs3() 함수로 구현하였다. 처음에 dfs2() 함수에서 dfs1() 함수를 재귀로 호출하는 멍청한 짓도 하였는데, 이는 가끔 발생하는 잔실수인 것 같다. 조심할 것. 전위 순회, 중위 순회, 후위 순회는 결국 어떤 것이 먼저 .. 더보기 2146번 2146번 - 다리 만들기 다리의 최솟값, 즉 최단거리를 구하는 것이고, 좌표내에서 이동은 비용이 1칸으로 동일하므로 BFS로 풀어야겠다는 생각을 하였다. 풀려고 하는데 입력값이 모두 1로 주어졌기 때문에 대륙간의 연결에 어려움이 있다고 생각했고, 대륙을 각각 다른 값으로 묶어줘야했기 때문에 처음에 BFS를 대륙을 다른 번호로 묶어주는 방식으로 사용했다. (대륙을 묶는 방식은 DFS를 사용해도 될 것 같다) 대륙을 묶은 값 = map2 대륙을 묶은 후에는 맵 전체에 대해서 BFS를 하였다. 단, BFS는 어떠한 대륙에서만 시작할 수 있다는 조건을 달았다. 그리고 BFS에서 바다로 다리를 놓다가 시작한 대륙의 번호와 다른 대륙을 만나면 그 값을 체크해서 가장 작은 값으로 업데이트 해줬다. 각각의 점들에 대.. 더보기 2178번 2178번 - 미로탐색 가장 간단한 BFS 구현 문제. 출발점에서 끝점까지 최소값을 구하는 것이고, 한점에서 다른 점으로 이동 비용이 1칸으로 동일하므로 BFS를 구현하여 최소값을 찾을 수 있다. 단, 이 문제에서 예제로 구한 답을 보면 시작점과 끝점을 모두 포함하기 때문에, dist 의 시작점 값이 0이 아니라 1로 초기화해서 문제를 풀었다. 입력으로 char 형을 받는건 앞에서 풀어본 문제와 동일하여 손쉽게 패쓰~ 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include#include#includeusing namespace std;int dx[4] = { 0,0,1,-.. 더보기 7576번 7576번 - 토마토 한 점에서 거리가 하루(1일)로 동일하게 퍼져나가므로 BFS 문제라고 볼 수 있다. 그리고 이에 따른 최소값을 묻는 문제이므로. 처음에 익은 토마토가 있는 하나의 정점에서 BFS를 수행한다. 그리고 익지 않은 토마토가 있는 각각의 점들에 대하여 dist 값, 즉 몇일 만에 토마토가 익는지 계산해본다. 그리고 또 다른 익은 토마토가 있는 정점에서 BFS를 수행한다. 이미 예전에 방문했던 점을 경우에는 dist값을 비교하여 적은 값으로 업데이트 해준다. 이런식으로 처음에 익은 토마토가 있는 모든 점에서 BFS를 수행하면 최소값을 계산할 수 있다. 다 익지 않는 경우는 익지 않는 토마토의 dist 값이 0 인 경우에는 모든 BFS 탐색에도 불구하고 그 토마토가 익지 않았다는 증거이므로 그.. 더보기 4963번 4963번 - 섬의 개수 2667번 보다 조금 더 쉬운 난이도의 문제였다. 단지 생각할 점은 대각선의 섬까지 걸어갈 수 있는 것으로 생각하기 때문에 dx,dy 를 대각선까지 포함시켜야 했다. 또한 습관적으로 입력값에 대해서 생각을 안했었는데 w,h 로 들어오는 값은 내가 코딩하는 방식과 반대여서 x값으로 h , y값으로 w를 써야했는데 간과했었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include#include#includeusing nam.. 더보기 이전 1 ··· 32 33 34 35 36 37 38 ··· 40 다음