알고리즘 문제 풀이/백준
-
[백준] 적록색약 - 10026번알고리즘 문제 풀이/백준 2021. 7. 8. 13:29
문제설명 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 기본아이디어 적록색약인 경우에는 R, G 가 같은 구역으로 보이고 아닌 경우는 모두 다른 구역으로 보입니다. 맵을 탐색하면서 구역으로 안 나뉜 경우 구역 수를 하나 늘려주고 bfs 탐색으로 같은 구역을 모두 0으로 초기화 시켜주면서 진행합니다. 모든 맵이 0이 되면 종료 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..
-
[백준] 치킨 배달 - 15686번알고리즘 문제 풀이/백준 2021. 7. 8. 13:29
문제설명 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 기본아이디어 맵에는 집과 치킨집이 존재한다. (1, 2로) 치킨집 중 M개를 선택했을 때 각 집들과의 거리의 합이 최소인 값을 구하면 된다.먼저 도시 정보에서 집과 치킨집 정보를 저장해두고 완전탐색으로 치킨집들 중 M개를 선택해서 집들과의 거리의 합을 계속해서 구하면서 최소값을 찾으면 된다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1..
-
[백준] 테트로미노 - 14500번알고리즘 문제 풀이/백준 2021. 7. 8. 13:29
문제설명 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 기본아이디어 결국은 모든 칸에 폴리오미노를 한번씩 모든 회전 가능한 방법으로 놓고 그때 가장 큰 값을 찾으면 된다.그래서 가능한 폴리노미노를 미리 배열로 만들어 놓고 그걸 확인하는 방법으로 했습니다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37..
-
[백준] 암호 만들기 - 1759번알고리즘 문제 풀이/백준 2021. 7. 6. 21:46
문제설명 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 기본아이디어 최소 한개의 모음과 최소 두개의 자음으로 구성된 길이 L인 문자열을 만들면 된다.사전순으로 출력을 해야하기 때문에 가능한 경우를 dfs 탐색으로 찾으면 된다. 선택된 문자들이 길이가 L이 되면 그때모음이 한개 이상이고 자음이 두개 이상인지 검사를 하고 통과하면 정답으로 출력을 해준다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..
-
[백준] 로봇 청소기 - 14503번알고리즘 문제 풀이/백준 2021. 7. 6. 21:46
문제설명 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 기본아이디어 로봇 청소기가 정해진 규칙에 따라 한칸 한칸 청소해 나가고 청소 가능한 곳을 다 탐색하면 종료한다. 일단 직진으로만 움직이는데 움직이지 못하는 상황에 따라 다른 행동을 하면 된다. 전형적인 시뮬레이션 문제입니다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32..
-
[백준] 탈출 - 3055번알고리즘 문제 풀이/백준 2021. 6. 29. 20:20
문제설명 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 기본아이디어 도착 지점에 도달하는 최소시간을 구하는 문제입니다. BFS 탐색으로 접근했습니다.문제는 조건에 "다음 시간에 물이 찰 예정인 칸으로 고슴도치를 옮길 수 없다." 라는 조건이 있습니다. 이 점을 유의해서 구현해야합니다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 3..
-
[백준] 주사위 굴리기 - 14499번알고리즘 문제 풀이/백준 2021. 6. 29. 20:20
문제설명 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 기본아이디어 결국 이동이 일어났을 때 주사위 상태가 어떻게 변하는지를 계속해서 바꾸어 주면 된다고 생각했습니다. 그래서 주사위가 이동했을 때 이전의 주사위에서 값이 변한 위치를 업데이트 시켜주는 것으로 문제를 해결했습니다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..
-
[백준] 인구 이동 - 16234번알고리즘 문제 풀이/백준 2021. 6. 28. 20:31
문제설명 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 기본아이디어 시뮬레이션 문제입니다. 나라 갯수가 작기 때문에 BFS 탐색을 통해서 인구 이동이 발생하는 나라 그룹을 만들고 인구이동 시키고 다시 그룹을 만들고 이런 방식으로 구현했습니다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3..