전체 글
-
백준 16929번 Two DotsPS 2020. 4. 14. 23:06
https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다. www.acmicpc.net 정점의 갯수가 4이상인 사이클의 존재 여부를 묻는 문제입니다. dfs를 돌면서 이미 방문한 지점도 확인해주어야 하는 문제였습니다. #include #include #include using namespace std; struct point { int y, x; }; int n, m; char map[51][51]; bool visit[51][51]; bool suc; in..
-
백준 dfs 스페셜 저지PS 2020. 4. 10. 01:37
https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다. www.acmicpc.net dfs로 방문할 수 있는지의 여부를 묻는 문제입니다. 다음 정점으로 이동할 때, 주어진 순서대로 갈 수 있으면 이동하고 마지막 정점에 도착하면 성공했다고 표시해줍니다. #include #include #include using namespace std; const int MAX = 100000; int n,..
-
백준 16973번 직사각형 탈출PS 2020. 4. 8. 21:00
https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 왼쪽 위칸은 (Sr, Sc)에 있을 때, 이 직사각형의 가장 왼쪽 위칸을 (Fr, Fc)로 이동시키기 위한 최소 이동 횟수를 구해보자. 격자판의 각 칸에는 빈 칸 또는 벽이 있다. 직사각형은 벽이 있는 칸에 있을 수 없다. 또한, 직사각형은 격자 www.acmicpc.net 사이즈가 있는 직사각형의 bfs입니다. 큐에 넣을때마다 2중 for문으로 확인 작업을 하면 시간초과가 납니다. bfs를 돌리기 ..
-
백준 16940번 BFS 스페셜 저지PS 2020. 4. 8. 20:56
https://www.acmicpc.net/problem/16940 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 그래프가 주어지고 bfs를 돌렸을 때, 나올 수 있는 방문 순서인가를 묻는 문제입니다. 방문 깊이?뿐만 아니라 큐에 들어간 순서를 고려해야 합니다. A-a B-b A, B가 동일 depth이고 a,b가 동일 depth일 때, A가 먼저 큐에 들어갔으면 A, B, a, b가 방문 순서가 되겠지요. q.front()의 결과로 나온 노드의 자식노드가 전부 나왔는가를 확인합니다. 이의 결과로 두 가지가 있습니다. 1. 만약 자식노드가 전부 나왔다. 이 경우는 자식노드를 큐에 넣어주는 순서를 입력받은 순서대로 하여 넣어줍..
-
백준 16957번 체스판 위의 공PS 2020. 3. 24. 12:55
https://www.acmicpc.net/problem/16957 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙에 의해서 자동으로 움직인다. 인접한 8방향 (가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다. 그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다. 공의 크기는 매우 작아서, 체스판의 한 칸 위에 여러 개의 공이 있을 www.acmicpc.net 접근 방법이 다양한 문제입니다. 저는 그냥 bfs, 우선순위 큐를 활용한 bfs, dp로 풀었습니다. 공은 큰 곳에서 작은 곳..
-
백준 5014번 스타트링크PS 2020. 3. 24. 12:51
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없 www.acmicpc.net bfs 완전탐색 문제입니다. 엘리베이터로 이동하므로 최소 층과 최대 층이 있음에 유의해야 합니다. #include #include #i..
-
백준 17069번 파이프 옮기기2PS 2020. 3. 22. 22:53
https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 www.acmicpc.net 완전탐색으로 할 경우 시간초과가 납니다. dp로 중복탐색을 없애야 합니다. #include #include #include ..
-
백준 16931번 겉넓이 구하기PS 2020. 3. 21. 04:49
https://www.acmicpc.net/problem/16931 16931번: 겉넓이 구하기 크기가 N×M인 종이가 있고, 종이는 1×1크기의 칸으로 나누어져 있다. 이 종이의 각 칸 위에 1×1×1 크기의 정육면체를 놓아 3차원 도형을 만들었다. 종이의 각 칸에 놓인 정육면체의 개수가 주어졌을 때, 이 도형의 겉넓이를 구하는 프로그램을 작성하시오. 위의 그림은 3×3 크기의 종이 위에 정육면체를 놓은 것이고, 겉넓이는 60이다. www.acmicpc.net 각 블록기둥의 겉넓이를 구해 모두 더해서 답을 구합니다. 블록기둥의 위아래는 무조건 각각 1 입니다. 블록기둥의 상, 하, 좌, 우는 붙어있는 블록기둥과의 높이차 입니다. 블록기둥을 입력받을 때 한 칸씩 띄워서 받아서 구현편의성을 높였습니다. #..