본문 바로가기

BOJ26

[BOJ] 백준 10971번 - 외판원 순회 2(with Java) 문제 알고리즘 1. 한 노드에서 다른 노드로 이동하는데 필요한 비용 데이터를 저장하기 위해서 인접리스트를 선언하고 값을 저장한다. 2. 최소 비용을 구하기 위해서 편의상 answer를 최대값으로 초기화 및 출발 지점 i를 방문처리하고 DFS를 시작한다. 3. DFS 메소드에서 매개변수 start와 인접한 각각의 노드까지의 이동 비용이 0이 아니고 방문하지 않았는지 확인한다. 4. 조건을 모두 만족하면 인접 노드 adj.idx를 방문처리 후에 i에서 출발하고 다시 돌아올 때까지 필요한 비용 sum에 인접 노드까지의 비용 adj.cost를 더해준다. 5. DFS를 수행할 때마다 start와 sum을 갱신하고 메소드를 빠져나올 때 다음 경우의 수를 확인하기 위해서 백트래킹을 수행한다. 6. target 노드를.. 2022. 6. 30.
[BOJ] 백준 2210번 - 숫자판 점프(with Java) 알고리즘 가능한 경우의 수를 찾는 문제이므로 정답 출력용 집합을 만들어준다. 각 위치에 대한 값이 모두 다를 수도 있고 이전에 방문한 위치를 재방문할 수 있으므로 전체에 대해서 DFS를 시작한다. 6자리 숫자를 만들어야하므로 다음 DFS를 수행할 때마다 nextVal을 통해서 값을 갱신하고 depth+1을 통해서 자릿수를 갱신한다. depth가 6이 되면 answer에 값을 추가하고 반환한다. 모든 위치에 대해서 위의 과정을 반복한 후에 answer의 크기를 출력한다. 소스코드 문제링크 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 21211.. 2022. 6. 30.
[BOJ] 백준 4963번 - 섬의 개수(with Java) 알고리즘 입력에 의해 프로그램의 종료가 결정되므로 while(true) 안에서 값을 입력받고 검사한다. 값이 유효하다면 각각의 위치에 대해서 값이 1이고 방문하지 않았는지 확인하고 DFS를 시작한다. 각 위치에 대해서 DFS를 수행한 이후에 cnt를 1씩 증가시키고 테스트케이스가 끝날 때마다 answer에 cnt를 추가한다. 1번에서 검사한 값이 유효하지 않으면 반복문을 탈출하고 answer에 포함된 값들을 순서대로 출력한다. 소스코드 문제링크 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 2022. 6. 30.
[BOJ] 백준 11060번 - 점프 점프(with Java) 알고리즘 미로에서의 현재 위치와 이동 횟수를 구하기 위해서 Node 클래스를 정의한다. 0번 이동한 상태에서 0번 위치에서 시작할 때 만들어지는 객체로 BFS를 시작한다. 현재 위치 idx에서 한번에 최대 arr[idx]만큼 이동할 수 있으므로 각각의 경우에 대해서 조건에 부합하는지 확인하고 탐색한다. 조건에 부합하면 방문처리해주고 다음 방문할 위치 idx와 time+1을 객체로 만들어서 큐에 넣어준다. 큐에서 꺼낸 객체의 번호가 끝 번호라면, 해당 객체의 time을 출력하고 종료한다. 소스코드 문제링크 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는.. 2022. 6. 30.
[BOJ] 백준 2667번 - 단지번호붙이기(with Java) 알고리즘 값이 1이고 방문하지 않은 각각의 위치에 대해서 방문처리해준 후에 DFS를 시작하고 types를 1 증가시킨다. DFS를 재귀적으로 수행할 때마다 cnt를 1씩 증가시키고, 재귀문을 빠져나오면 answer에 cnt 값을 추가한다. cnt를 재사용하기 때문에 cnt를 0으로 초기화해주고, 위의 과정을 모든 위치에 대해서 반복한다. answer를 오름차순으로 정렬해준 후에 types와 함께 출력한다. 소스코드 문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2022. 6. 28.
[BOJ] 백준 2606번 - 바이러스(with Java) 알고리즘 1번 컴퓨터에서 시작하므로 방문했음으로 처리한 후에 1번에 대해서 DFS를 수행한다. DFS 이후에 visited 배열에서 값이 true인 원소의 개수만큼 answer를 1 증가시킨다. 감염된 컴퓨터의 개수에 대해서 묻고 있으므로 answer의 값이 1이상이면 answer에서 1을 빼준 후에 출력한다. 소스코드 문제링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2022. 6. 28.
[BOJ] 백준 18405번 - 경쟁적 전염(with Java) 알고리즘 바이러스의 위치와 몇 초에 바이러스가 퍼졌는지 계산하기 위해서 Virus 클래스를 생성한다. 배열의 원소를 입력받을 때 값이 1이상인 경우에 대해서 grid[i][j]에 해당하는 인접 리스트에 좌표값을 갖고 있는 Virus 객체를 각각 삽입한다. 1부터 K까지의 바이러스 번호를 보유한 인접리스트로부터 좌표값을 갖고 있는 Virus 객체를 큐에 각각 추가한다. BFS를 수행하면서 다음 위치로 이동할 수 있을 때마다 좌표값과 현재 바이러스가 퍼지기까지 걸린 시간으로 Virus 객체를 구성한다. 위의 과정을 바이러스가 퍼지기까지 걸린 시간이 S인 Virus 객체를 큐에서 꺼낼 때까지 수행한다. 소스코드 문제링크 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다... 2022. 6. 28.
[BOJ] 백준 1697번 - 숨바꼭질(with Java) 알고리즘 N에서 BFS를 시작한다. 가장 빨리 찾은 시간을 게산하기 위해서 idx와 time을 원소로 가지는 Node 클래스를 생성한다. 총 3가지의 행동 X-1, X+1, X*2을 할 수 있으므로 각각의 경우에 대해서 이동할 수 있는지 확인한 후에 방문 처리 및 time을 1 증가시켜서 큐에 넣어준다. 큐에서 꺼낸 node.idx의 값이 K와 일치하면 answer에 값을 저장하고 반복문을 탈출한다. 소스코드 문제링크 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 2022. 6. 28.
[BOJ] 백준 2644번 - 촌수계산(with Java) 알고리즘 1. BFS를 할 때마다 특정 번호의 촌수를 계산하기 위해서 Node 클래스를 선언한다. 2. 먼저 주어지는 사람의 번호를 src, 나중에 주어지는 번호를 dsc라고 정의한다. 3. 주어진 값들을 입력받을 때 아직 촌수를 알 수 없기 때문에 각 번호에 대한 촌수를 0으로 초기화한다. 4. BFS로 dst를 찾을 때까지 각각의 Node를 탐색하면서 cur.degree를 1씩 더하는 방식으로 번호들의 촌수를 초기화한다. 5. 큐에서 꺼낸 Node의 번호가 dst와 같으면 cur.degree를 반환한다. 6. 만약에 모든 Node를 탐색할 때까지 dst를 찾지 못하면 -1을 반환한다. 소스코드 문제링크 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각.. 2022. 6. 26.
[BOJ] 백준 1260번 - DFS와 BFS(with Java) 알고리즘 1. DFS와 BFS로 탐색한 결과를 저장하기 위해서 'dfsAnswer', 'bfsAnswer'를 각각 리스트로 만든다. 2. 방문할 정점이 여러 개인 경우, 값이 작은 정점을 먼저 방문하므로 각각의 인접리스트를 오름차순으로 정럴현다. 3. DFS, BFS를 통해서 도출된 결과들을 각각 'dfsAnswer', 'bfsAnswer'에 넣어주고 탐색이 모두 끝나면 한번에 출력한다. 소스코드 문제링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 2022. 6. 26.

티스토리툴바