[백준 / C언어] 14940번: 쉬운 최단거리 (BFS)

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 및 구현 목표 지점인 2부터 BFS을 시작해서 목표 지점까지의 거리가 몇 인지 visited에 적어준다. BFS 탐색을 끝내고 나서는 map = 0(= 갈 수 없는 땅)이 아니면서 visited가 0인 지점은 도달하지 못하는 곳을 의미하므로 해당 부분의 visited는 ..

• format_list_bulleted PS/백준
• · 2023. 7. 2.
• textsms

[백준 / C언어] 1358번: 하키

https://www.acmicpc.net/problem/1358 1358번: 하키 첫째 줄에 수 W H X Y P가 주어진다. P는 선수의 수이다. W와 H는 100보다 작거나 같은 자연수이고, H는 짝수이다. X와 Y는 절댓값이 100보다 작거나 같은 정수이다. P는 최대 50인 자연수이다. 둘째 줄부 www.acmicpc.net 난이도: solved.ac 실버 4 알고리즘 분류 기하학 접근 방법 주어진 P개의 좌표와 두 원의 중심 좌표 사이의 거리를 각각 구해서 각 원의 반지름의 길이보다 작거나 같으면 링크에 포함된다고 보았다. 그리고 직사각형 안에 들어도 링크 안에 포함되므로, 위의 두 원 안에 포함되지 않는다면 W * H 크기의 직사각형 영역 안에 포함되는지도 파악해 영역 안에 든다면 링크 안에..

• format_list_bulleted PS/백준
• · 2023. 7. 2.
• textsms

[백준 / C언어] 1074번: Z

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 재귀, 분할 정복 접근 방법 및 구현 찾아야 할 r행 c열의 숫자가 4등분 한 사각형 중 어느 부분에 있는지에 집중했다. 그리고 찾아야 할 좌표를 목표로 N = 0의 크기 즉, 한 칸짜리의 사각형이 될 때까지 4등분 해주었다. N = 3일 때 2행 5열의 숫자를 찾아야 한다고 해보자. N = 3일 때는 아래의 그림처럼 0~7행, 0~7열을..

• format_list_bulleted PS/백준
• · 2023. 7. 2.
• textsms

[백준 / C언어] 11724번: 연결 요소의 개수 (DFS로 풀이)

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 난이도: solved.ac 실버 2 알고리즘 분류 그래프 탐색, DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 구현 노드를 방문하면 visited에서 해당 노드의 값을 1로 바꾸고, 해당 노드와 연결된 다른 노드로 DFS 함수를 통해 탐색하였다. 그리고 더 이상 연결된 노드가 없을 때까지 DFS 함수를 재귀호출하도록 하였다. 연..

• format_list_bulleted PS/백준
• · 2023. 7. 2.
• textsms

[백준 / C언어] 7562번: 나이트의 이동 (BFS 풀이)

https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 최소 이동 횟수를 구하는 문제이므로 BFS로 접근하였다. 구현 위의 그림처럼 1시 방향부터 시작해 11시 방향까지 시계 방향으로 이동시키는 것을 한 단계로 큐에 넣어주었다. 방문한 좌표는 visited에 몇 번째로 이동한 건지 적어주었다. 코드 #define _CRT_SECURE_NO_WARNINGS #include..

• format_list_bulleted PS/백준
• · 2023. 7. 1.
• textsms

[백준 / C언어] 1697번: 숨바꼭질 (BFS 풀이)

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그래프 탐색 (BFS) 구현 방법 수빈이의 위치와 이동 횟수(찾는 시간)를 저장할 구조체 LOC를 만들어주었다. BFS에서 사용할 큐는 LOC형 배열로 만들어주었고 index는 100001까지로 해주었다. 내 풀이에서 주목해야 할 점이 있는데 -1 만큼 이동할 때 loc가 0보다 작아지면 안 되는 것이고, +1 만큼 이동..

• format_list_bulleted PS/백준
• · 2023. 7. 1.
• textsms