본문 바로가기
반응형

PS/백준

 (318)
[BOJ] 백준 7562 나이트의 이동 (Swift) 문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 BFS로 풀이할 수 있는 문제입니다. 체스판의 크기가 주어지면, l * l 크기의 2차원 Bool 배열을 만들어주었고, false로 초기화하였습니다. 이 2차원 배열을 나이트가 이동하는 경로를 확인 용도로 사용하려고 합니다. 또한 나이트는 8방향으로 움직일 수 있으므로, 8방향을 dy, dx라는 상수로 값을 주었습니다. BFS를 할 때, 처음 큐에 초기 나이트의 y, x 좌표와 이동한 횟..
[BOJ] 백준 1697 숨바꼭질 (Swift) 문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 BFS로 풀 수 있는 문제입니다. x - 1, x + 1, 2 * x 로 이동이 가능한데, 모두 1초씩 걸리므로, 비용이 동일하다는 것을 알 수 있습니다. 비용이 동일할 때, 최단 경로는 BFS로 구할 수 있어서 BFS로 풀이했습니다. 초기의 queue에 수빈이의 위치와 0초를 tuple의 배열 형태로 넣어주고, x - 1, x + 1, 2 * x 만큼 떨어진..
[BOJ] 백준 2178 미로 탐색 (Swift) 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 BFS를 사용하여 풀 수 있는 문제입니다. BFS는 간선의 비용이 동일할 때, 최단 경로로 방문한다는 특징이 있습니다. 물론 DFS + 백트래킹을 사용하여 모든 경로를 구해 답을 구할 수는 있겠지만, 100 * 100 크기이고, 모든 수가 1로 되어있다는 등 최악의 경우를 고려하면 시간초과가 날 것입니다. 그래서 BFS로 접근하여 풀었습니다. BFS 하면서 queue에 y, x 좌표와 얼마만큼 이동했는지 depth라는..
[BOJ] 백준 1012 유기농 배추 (Swift) 문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 DFS 또는 BFS를 사용하여 풀 수 있는 문제입니다. 문제에서는 입력을 위치로 주어지고 있습니다. 저는 2차원 Bool 배열을 사용해 해당 위치를 true로 주었습니다. 해당 위치를 탐색했는지 확인하기 위해 2차원 Bool 배열을 선언하였고, 지렁이가 상하좌우로 이동할 수 있기 때문에 방향을 설정할 dy, dx 배열을 선언해주었습니다. 탐색을 하기 전 마지막으로 범위를 벗어나는지 확인하기 위한 함..
[BOJ] 백준 2667 단지번호붙이기 (Swift) 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 DFS 혹은 BFS를 사용하여 풀 수 있는 문제입니다. 좌표의 방문 여부 확인하기 위해 2차원 Bool 배열을 선언하였습니다. 상하좌우로 이동이 가능하기 때문에 dy 값과 dx 값을 4방향 (동남서북) 으로 선언해주었습니다. 또한 지도의 범위를 넘어가는 경우를 막기 위해 함수를 작성해주었습니다. 그 이후 DFS 혹은 BFS를 사용해줍시다. 현재 좌표에서 상하좌우 중 이동이 가능하고, 아직..
[BOJ] 백준 1260 DFS와 BFS (Swift) 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 문제 그대로 DFS와 BFS를 사용하여 풀 수 있는 문제입니다. 주의할 점은 정점 번호가 작은 순으로 방문해야 하기 때문에, 인접 그래프를 정렬해주었습니다. DFS, BFS를 수행하면서 노드를 방문하게 될 떄, 해당 노드의 번호를 출력하도록 하였습니다. DFS를 먼저 수행하기 떄문에, DFS를 수행한 후, 방문 여부를 알 수있는 배열을 전부 fals..
[BOJ] 백준 2606 바이러스 (Swift) 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 DFS/BFS를 사용해서 풀이할 수 있는 문제입니다. 둘 중 아무거나 사용해도 상관없어서 두 방법으로 모두 풀어보았습니다. 먼저 정점의 개수만큼 방문 여부를 알 수 있는 Bool 배열을 선언해주었습니다. 탐색을 마친 후, 방문 배열을 확인하여 방문횟수를 구한 후, 1번 컴퓨터는 제외해야 하므로 1을 빼고 출력해주었습니다. 소스코드 후기 DFS/BFS의 기초적인 문제였습니다.
[BOJ] 백준 24445 알고리즘 수업 - 너비 우선 탐색 2 (Swift) 문제 https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 https://dev-mandos.tistory.com/255 [BOJ] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 (Swift) 문제 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,..
반응형

티스토리툴바