Let's Begin Programming

www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프의 종류 중 하나인 이분 그래프를 판별하는 문제이다. 이분 그래프는 한 정점으로부터 이동한 정점들 사이에서 BFS가 또 수행되면 성립하지 않는다. 즉, 한 정점에서 이미 방문한 정점에 대해 방문했을 때 그 정점이 같은 정점으로부터 방문 받은 정점이라면 이분 그래프가 아닌 것이다. 이를 체크하기 위해서 한 정점으로부터 이동할 때마다 방문을 체크하는 visited 리스트에 두 가지의 숫자를 넣어서..

개발 공부 (알고리즘) 2021. 2. 1. 05:03

www.acmicpc.net/source/25783143 로그인 www.acmicpc.net 언뜻 보면 기존의 문제들과 달라 보이지만 결국 유사한 문제이다. 단순하게 이동하는 방법이 변화했다고 생각하면 쉽게 풀린다. 기존에는 주로 x나 y값에 1을 더하거나 빼는 방식으로 인접한 정점으로 이동했다. 나이트는 두 칸을 상, 하, 좌, 우로 이동한 후에 이동한 방향에 좌 혹은 우로 한 칸 움직이는 방식으로 이동한다. 기존에 미리 정해 놓았던 x와 y 값의 움직임을 나이트의 움직임대로 8가지로 저장해놓으면 된다. 한 정점에서 범위를 벗어나거나 이미 방문한 정점을 제외하고 나이트의 움직임 8가지에 대해 BFS를 수행하면서 목표 위치까지 이동하는 갯수를 센다. [소스코드] from collections import..

개발 공부 (알고리즘) 2021. 2. 1. 04:18

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 앞에서 풀었었던 최단 거리에 특정 목표 지점까지 이동하는 문제들과 같은 맥락의 문제이다. 시작 지점은 항상 같은 위치로 정해져 있고 목표 위치만 입력에 따라 변한다. 다른 문제들과 다른 점은 벽을 한 번 부술 수 있는 "필살기"가 존재한다는 것이다. 시작점에서 출발해서 목표 위치까지 이동할 때 최단 거리로 갈 수 있다면 이동할 수 없는 위치로 이동할 수 있다. 일단 전체적인 문제의 구조..

개발 공부 (알고리즘) 2021. 2. 1. 02:38

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이 문제는 시작 위치와 목표 위치를 입력 받아 이동하는 최소한의 횟수를 구하는 문제이다. 한 정점 x에서 이동 가능한 지점을 미리 정의하고 BFS를 이용했다. 이동 가능한 위치의 정점이 범위를 벗어나거나, 이미 방문한 정점인 경우는 무시하고 방문이 가능할 경우에는 현재 정점의 값에서 1을 더하면서 이동한다. 한 번 이동할때마다 값을 증가시켜서 최종 필요 시간을 알 수 있게한다. 만약 ..

개발 공부 (알고리즘) 2021. 2. 1. 01:55

www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이전에 해결했었던 토마토 문제의 3차원 버전이다. 2021/01/31 - [개발 공부 (알고리즘)] - [백준] 7576번 - 토마토 (DFS, BFS) - 결과 포함 [백준] 7576번 - 토마토 (DFS, BFS) - 결과 포함 www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 ..

개발 공부 (알고리즘) 2021. 2. 1. 01:35

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 토마토 문제는 처음에는 얼마 안 걸릴 줄 알았던 문제이다. 하지만 "시간 초과"라는 결과를 받으면서 해결하는데 꽤 오랜 시간이 걸렸었다. 우선 토마토가 인접한 토마토들을 익게 하기 때문에 BFS를 이용해 그래프 순회를 해야겠다고 생각했다. 주어진 그림도 그래프를 의미하고 있다고 생각했기 때문이다. 먼저 BFS를 이용해 범위를 벗어나거나 토마토가 없는 곳, 이미 익은 곳은 무시하고 지나가도록 했다..

개발 공부 (알고리즘) 2021. 1. 31. 05:36

www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 미리 주어진 미로를 그래프라고 생각하고 주어진 위치 (N, M)까지 최소 거리로 이동하는 문제이다. 전형적인 BFS 문제로 (0, 0)부터 BFS를 시작해서 최종 목적지까지 이동하면 된다. 상, 하, 좌, 우로 이동하면서 다음 위치가 범위를 벗어나거나 이미 방문한 경우, 이동할 수 없는 위치인 경우에는 무시한다. 만약 이동할 수 있는 곳인데 아직 방문하지 않은 곳이라면 큐에 삽입하고 해당 정점의 값은 현재 내가 머물러 있는 위치의 정점 값에 ..

개발 공부 (알고리즘) 2021. 1. 31. 05:03

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이전에 풀었었던 '바이러스' 문제와 유사한 문제로 그래프에서 1로 이루어진 구역이 몇 개인지 구하는 문제이다. 먼저 1이 어디에 있을지 모르기 떄문에 모든 정점에서 출발해야 한다. 단, 이미 방문하거나 배추가 심어져 있지 않은, 0인 정점은 방문하지 않아도 된다. 정점에서 이동 가능한 방향은 상, 하, 좌, 우 4 방향이다. 방향을 미리 정해놓고 방문하지 않은 정점마다 반복문을 4번 돌면서 다음에 갈 정점을 정한다. 나는 ..

개발 공부 (알고리즘) 2021. 1. 31. 04:55