[백준] 1976: 여행가자 (BFS, 그래프탐색) - JAVA

골드 3~4 무작위 풀이https://www.acmicpc.net/problem/1976 너무 오랜만에 문제풀이 블로그를 작성한다 ! (사실 오랜만에 문제를 풀었다)지피티, 구글링을 안 하고 하려니까 오래 걸리는 문제들도 많고 ,,, 이래저래 할거도 많아서 소홀해진듯 다시 매일 풀어야겠다 # 문제 # 필요개념처음 문제를 봤을 땐 복잡하게 느껴졌다. 현재 시작점에서 다음 경로까지 길이 있는지 탐색하고, 있으면 또 다음 경로까지 길이 있는지 탐색하고.... 같은 도시를 여러번 갈 수도 있다고 하니 방문여부 체크는 불필요 할 거 같고,, 안 하자니 시간이 오래걸릴 거 같아서 고민이 되었다. 그런데 끄적이면서 생각해보니, 그냥 시작점에서 연결된 모든 지역을 탐색하고 내가 가려는 도시가 첫 도시와 연결되어있..

class 6https://www.acmicpc.net/problem/13334   # 문제  # 필요개념배열에 담아서 정렬하면 편한 문제겠지만 시간이 1초라서 O(n^2) 가 되면 시간초과가 발생한다. 혹시나 해봤지만 역시나이니 시도하지 않아도 된다. 이렇게 일정 간격을 순회해야 할 경우 투포인터를 응용하여 문제를 풀 수 있다. 이 문제는 일정 간격(dis) 안에 집과 회사가 모두 들어있는 루트의 개수를 구해야 하는 문제이다. 푸는 기본적인 로직은 다음과 같다.입력받은 수를 저장할 이차원 배열과 실제 문제풀이에 이용할 리스트를 각각 생성한다.숫자 두개를 입력받되, 작은 것을 집, 큰 것을 회사라고 가정한다. 입력을 받을 때 작은 숫자가 앞에 오지 않는 경우도 있기 때문에 애초에 배열에 저장할 때 min..

class 6https://www.acmicpc.net/problem/14725   # 문제# 필요개념이 문제는 결론적으로 노드들의 깊이를 오름차순으로 도출해야하는 문제이기 때문에 dfs를 사용하였다. 평소 그래프 문제를 풀 때에는 이중 리스트를 만들어 풀었지만, 이 문제는 이름이 같은 노드가 존재할 수 있고, 깊이라는 개념이 도입되기 때문에 이중리스트로 풀지 않았다.  A노드의 자식노드인 B노드에게 C라는 자식노드가 존재한다고 가정할 때, A노드에게 C라는 자식노드가 있을 수 있다. 이 두 노드는 이름만 같을 뿐, 아예 다른 노드이기 때문에 그래프문제처럼 풀면 안 된다. Node라는 클래스를 만들고, 여기에 자신의 값과 children을 넣어주었다. children에 값을 추가하는 것은 별도의 메소드 ..

알고리즘 분류 (그래프 탐색)https://www.acmicpc.net/problem/7569   # 문제 # 필요개념지금까지 했던 2차원 배열 탐색과 달리, 토마토가 들어있는 3차원 상자를 탐색해야 한다. 그래서 삼차원 배열을 생성해주었다. 지금까지 BFS로 그래프탐색을 할 때 방문 여부를 확인하는 isVisit 배열을 생성했었는데, 이 문제는 애초에 전체 토마토를 익게 할 수 있는 "시간" 을 물어보고 있기 때문에, 시간을 넣어줄 배열(map)을 생성해주었다. 토마토 입력이 0인 자리에 초기값을 -1로 설정해주어서 -1이면 방문하지 않은 곳임을 알 수 있도록 했다. 모든 익은 토마토들은 동시에 주변을 익게 만들기 때문에, 입력이 1인 토마토들을 일단 모두 Queue에 담고, 다 담은 후에 bfs 탐색..

알고리즘 분류 (dfs)https://www.acmicpc.net/problem/1707  # 문제  # 필요개념이 문제를 풀기 위해서는 이분 그래프의 개념에 대해 먼저 이해해야한다. 개념 공부를 제대로 하지 않고 접근했다가 내 정답률만 잔뜩 낮춰버렸다 😇 그래서 개념 정리겸 블로그 작성 완료 ! 아래 링크를 걸어두었다https://wanna-developer02.tistory.com/191 [Data Structure] Bipartite Graph (이분 그래프) | 자바백준 문제를 풀다가 처음보는 자료구조를 정리하려고 한다. "이분" 이라는 단어가 들어가는 자료구조들이 꽤 있는 만큼, 개념을 헷갈리지 않게 정리하는 것도 중요하지 않나 싶다. 순서는 간단wanna-developer02.tistory...

알고리즘 분류 (dfs)https://www.acmicpc.net/problem/1520   # 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아..

class 6https://www.acmicpc.net/problem/2533   # 문제페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다.  친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로..

class 6https://www.acmicpc.net/problem/2357   # 문제N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.  # 예제입력 :  첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가..

단계별 문제풀이 23단계 (동적계획법1)https://www.acmicpc.net/problem/11054   # 문제수열 S가 어떤 수 Sk를 기준으로 S1    > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.  # 예제입력 :  첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄..

단계별 문제풀이 (23단계)https://www.acmicpc.net/problem/2565   # 문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남..