lee-soo 님의 블로그

https://www.acmicpc.net/problem/16929 문제에 대한 이해는 넘어가겠다 그냥 사이클이 돌리는 문자들이 있으면 된다는 거고 그렇다면 이건 딱봐도 dfs일것이다bfs가 아닌 이유는, 너비 우선 탐색으로 가면 그 주위 값들을 먼저 확인하는 거기 때문에, AAAA이렇게 있을 경우0,0에서 시작하면1,0 0,1의 A를 찾고이후 VISITED된 A는 다시 못돌아가기때문에1,1에 있는 A로 가면 결국 찾을 수 없다 뭐 이런건 넘어가고DFS로 가면 최대한 깊은곳으로 가서 BACK TRACKING이 가능하다 정말 정말 간단한 방법으로그냥 입력받고 dfs를 돌때마다 근접한 값이 같은색깔이고 visit하지 않았나?를 살펴본다 그 이후 dfs의 초반 부분에는 만약 start 부분하고 같으면 오우~..

https://www.acmicpc.net/problem/7562 나이트의 이동 [DFS,BFS] 백준 7576번 토마토(C++) [DFS,BFS] 백준 7576번 토마토(C++)https://www.acmicpc.net/problem/7576 멋쟁이 토마토 토마토 내용은 쉽다1의 번짐이지 퉁퉁퉁퉁퉁사후르 같은거 기대하고 토마토그려달라햇는데토마토가 토마토를 먹는 그림이 나옴무서워 잡설은 그만lee-soo.tistory.com이 문제는 토마토 문제를 꼭 풀고 와야 된다왜냐면 그 코드 위주로 수정해서 풀었거든 내용은 쉽다 어라그냥...나이트가 해당 체스판으로 가는 최소 움직임의 수를 구하면 되네? 예제하나를보면8 * 8 체스판안에서0,0 -> 7,0으로 가는 최단 경로의 수는?이제 빨간색에서 파란색으로 이..

https://www.acmicpc.net/problem/7576 멋쟁이 토마토 토마토 내용은 쉽다1의 번짐이지 퉁퉁퉁퉁퉁사후르 같은거 기대하고 토마토그려달라햇는데토마토가 토마토를 먹는 그림이 나옴무서워 잡설은 그만하고[DFS,BFS] 백준 1260번 BFS와 DFS(C++) [DFS,BFS] 백준 1260번 BFS와 DFS(C++)https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그lee-soo.tistory.com당연히 bfs 문제인데 다른점이 있다 먼저 생각해야 될 게 1. 1인 곳을 먼저 파악하고 ..

https://www.acmicpc.net/problem/2178 [DFS,BFS] 백준 1260번 BFS와 DFS(C++) [DFS,BFS] 백준 1260번 BFS와 DFS(C++)https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그lee-soo.tistory.combfs로 풀어야 되는 문제이다 지나야 하는 최소의 칸 수를 입력하라 했고,그걸 bfs로 찾아가는 문제~dfs로 하면 가장 깊은 방법으로 가기때문에예를들어1 1 11 1 11 1 1이 있을경우00 > 01 >02> 12 >11> 10 >20 ..

https://www.acmicpc.net/problem/4963 [DFS,BFS] 백준 2667번 단지 번호 붙이기(C++) [DFS,BFS] 백준 2667번 단지 번호 붙이기(C++)https://www.acmicpc.net/problem/2667 [DFS,BFS] 백준 1260번 BFS와 DFS(C++) 이문제, 당연히 BFS와 DFS 문제를 풀고 와야 겠지? 내용 자체는 쉽다그림으로만 딱 봐도 보이잖나?그럼 어떻게 풀까? 앞선 BFS나 DFS문제들lee-soo.tistory.com혹은 [DFS,BFS] 백준 1260번 BFS와 DFS(C++) [DFS,BFS] 백준 1260번 BFS와 DFS(C++)https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 ..

https://www.acmicpc.net/problem/2667 [DFS,BFS] 백준 1260번 BFS와 DFS(C++) 이문제, 당연히 BFS와 DFS 문제를 풀고 와야 겠지? 내용 자체는 쉽다그림으로만 딱 봐도 보이잖나?그럼 어떻게 풀까? 앞선 BFS나 DFS문제들에선 연결된 NODE들을 통해서 그래프를 그렸는데 이번에도 똑같다연결된 노드들끼리의 배열이 아닌 연결된 노드들의 갯수만 보면 됨~ 하지만 앞선 문제들은 모두 1차원인데 이건 2차원이다 그럼 어떻게 풀까? 1. 2차원으로2. 1차원으로 뭔가 반대가된 기분이네쨋든 2차원으로 푸는건 쉽다bfs 와 dfs로 들어갔을 때 , 그저 queue> q 만 새로 해줘서쌍으로 저장하면 되지만 나는 그걸 몰랐다풀고나서, 인터넷 찾아보니까 저런게 있더라..

https://www.acmicpc.net/problem/1707 장난 아니다.이게 무슨 문제인것인가...예시를 봐도 이해가 안간다... [DFS,BFS] 백준 1260번 BFS와 DFS(C++)앞선 dfs와 bfs를 꼭 풀고오길 https://hongjw1938.tistory.com/117 자료구조 - 이분 그래프(Bipartite Graph)관련 글 그래프 관련 글은 여기를 참조 그래프 탐색 - BFS는 여기를 참조 그래프 탐색 - DFS는 여기를 참조 1. 이분 그래프 이분 그래프는 그래프 형태의 자료구조인데 정점을 2그룹으로 나눌 수 있hongjw1938.tistory.com참고한 사이트이다. 해당 사이트에서 설명한 것 처럼 모든 노드들이 이렇게 2가지 형태로 나뉘는 것이고, 같은 집합에 속하..

https://www.acmicpc.net/problem/11724짜잔 난 솔직히 이거 처음 봤을때 뭔소린가 했다.연결 요소란 개념을 먼저 알고 있어야 한다 연결요소는 간단하다 앞선 BFS , DFS에서 우리는 그래프 개념을 사용해서 문제를 풀었고 [DFS,BFS] 백준 1260번 BFS와 DFS(C++) [DFS,BFS] 백준 1260번 BFS와 DFS(C++)https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그lee-soo.tistory.com안풀어봤으면 꼭 풀어보고 와라 각 노드들은 서로 연결되어 ..

https://www.acmicpc.net/problem/1260BFS와 DFS라는 개념에 대해서 아는가? 예제를 통한 예시를 보여주겠다 먼저 1,2 1,3 1,4 2,4 3,4라는 edge가 있는 경우를 그래프로 나타내보겠다 대략 이렇게 그려져 있다 그리고 문제내부에 보면 정점 번호가 작은것을 먼저 방문한다고 했다 그리고 bfs와 dfs에 대한 간략한 설명을 하자면 bfs : 현재 노드에서 방문할 수 있는 점을 먼저 모두 방문, 그 이후 연결된 점을 또 시작으로 방문가능한 모든 점을 방문(작은순서로) dfS:현재 노드에서 가장 깊에 들어갈 수 있는 점을 방문, (한 방향으로 끝까지) 막히면 되돌아와서 다른길을 탐색 그림으로 bfs를 먼저 설명해 주겠다입력상 1을 먼저 탐색하게 되니당연히 1이 먼저 들어..

https://www.acmicpc.net/problem/13023 코테 준비를 할때마다 느끼는 건데, 진짜 30분안에 안풀리면 무조건 답지를 보자.오히려 내 방식대로 풀려다가 1시간 2시간 지나고 못풀면 그 자괴감이 더 크다. 심지어 푸는 방식도 달라서 내 접근법이 아예 틀렸을땐 정신적인 타격또한 후... 그나마 오늘푼건 1시간정도 끙끙대쓴데, 접근법은 맞아서 50%정도만 아팠다 내용은 간단하다 각 친구관계 사이가 주어졌을때 5명이 이어져서 친구인 관계가 존재하는가? 나는 여기서 어라, 이거 dfs로 depth 가 4일때 끊으면 되는거 아닌가? 생각하고그 각 값을 저장해줄 struct를 따로 만들어 보자고 생각했다 예를들어 struct s{bool arr[2000]} 을 하고, s를 배열로 정하는 거..