자바(Java) 백준 13460 구슬 탈출 2 풀이
2022. 7. 26. 00:54
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 이 문제는 Bfs를 사용하여 풀었습니다. 생각해줄 조건이 조금 까다롭습니다. 두 구슬을 동시에 움직이므로 생각해줘야 할게 많아진 것 같습니다. 먼저 빨간 구슬과 파란 구슬의 초기 위치를 저장합니다. 큐에 정보를 넣기 위해 빨간 구슬의 위치, 파란 구슬의 위치, 움직인 횟수 정보를 가지고 있는 PairBeads 클래스를 만듭니다. bfs는..
자바(Java) 백준 1062 가르침 풀이
2022. 7. 25. 15:06
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 저는 dfs와 조합으로 문제를 풀었습니다. 학생들이 어떤 알파벳을 배웠는지 알 수 있는 aplhaArr라는 boolean 배열을 만들어줍니다. 문제에서 anta, tica 두개의 접두사와 접미사가 단어 안에 무조건 들어가야합니다. 따라서 a, n, t, i, c 5개의 알파벳은 학생들이 배우지 않는다면 어떤 단어도 읽을 수가 없습니다. 따라서 k가 5개 미만이라면 어떤 단어도 읽..
자바(Java) 백준 4574 스도미노쿠 풀이
2022. 7. 18. 16:54
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/4574 4574번: 스도미노쿠 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 채워져 있는 도미노의 개수 N이 주어진다. (10 ≤ N ≤ 35) 다음 N개 줄에는 도미노 하나를 나타내는 U LU V LV가 www.acmicpc.net 풀이 dfs 문제인데 조건이 생각보다 까다로워서 코드 작성하는데 시간이 좀 걸렸습니다.. 제가 이 문제를 푼 과정은 다음과 같습니다. 도미노를 체크해줄 2차원 배열이 필요합니다. visitedDomino[a][b]에서 a와 b는 도미노에 들어있는 숫자를 의미합니다. visitedDomino[b][a]도 체크해줍니다. 먼저 입력으로 받은 도미노와 숫자들을 2차원 배열에 값을 입..
자바(Java) 백준 2580 스도쿠 풀이
2022. 7. 15. 21:45
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 9 * 9의 네모안에서 값이 0인 지점들을 스도쿠 규칙에 따라 올바른 숫자로 채우는 문제입니다. 스도쿠 규칙은 다음 3가지를 충족하면 됩니다. 가로 9칸의 숫자가 모두 달라야합니다. 세로 9칸의 숫자가 모두 달라야합니다. 3 * 3의 작은 네모안에 있는 9칸의 숫자가 모두 달라야합니다. 다음의 순서로 풀이합니다. 0 값을 갖고 있는 지점들을 List에 저장합니다. dfs를 통해 list..
자바(Java) 백준 9663 N-Queen 풀이
2022. 7. 15. 20:05
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 유명한 N-Queen 문제를 풀면 된다. 예전에 대학교 알고리즘 수업 때 c++로 백트래킹을 써서 풀어 본적이 있었는데 이번에 자바로 다시 한번 풀어보았다. 제가 푼 방식은 다음과 같습니다. 1) 세로로 인덱스 0부터 n - 1까지 퀸을 하나씩 배치할 것입니다. 2) dfs를 사용하여 세로 -> 가로 순으로 0 ~ n - 1까지 해당 지점에 퀸을 놓을 수 있는지 확인합니다. 3) isPos() 메서드를..
자바(Java) 백준 16198 에너지 모으기 풀이
2022. 7. 15. 15:10
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net 풀이 간단하게 dfs로 풀었습니다. 여기서 중요한 부분은 구슬들을 리스트에 넣고 중간에 있는 구슬을 삭제해야 되는 부분이 있는데 자바의 list.remove()와 list.insert()는 O(n)이 걸리는 연산이기 때문에 시간초과가 날 수 있으므로 주의해서 사용해야 합니다. 이 문제에서는 n 값이 최대 10이므로 시간초과가 발생하지 않을 것이라고 생각하고 사용하여 풀었습니다. 코드 i..
자바(Java) 백준 16197 두 동전 풀이
2022. 7. 15. 15:09
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 풀이 움직임의 최소값을 찾는 문제이므로 bfs를 사용해서 풀이했습니다. 제가 사용한 풀이 방법은 1) 두 동전의 위치를 찾아서 pair에 저장해둔다 2) bfs를 사용하여 큐에 값을 넣어주고 4가지 방향으로 움직일 때 조건에 맞으면 새로운 좌표를 큐에 넣습니다. 이 때 방문 했는지 여부를 확인하기 위해 4차원 배열 visited를 사용하여 두 동전의 위치를 체크합니다. 3) 움직인 좌표가 ..
자바(Java) 백준 14500 테트로미노 풀이
2022. 7. 15. 15:08
알고리즘 풀이/백준
문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 이 문제는 5가지의 도형중에서 분홍색 도형은 따로 해결해주고 나머지 4가지 도형은 dfs로 풀면 됩니다. 1) 나머지 도형 2차원 배열을 이중 for문으로 돌면서 각 점마다 dfs를 진행합니다. dfs는 첫번째 점 좌표를 넘겨주고 방문체크를 하면서 총 4개의 점을 방문 했을 때 합을 구해 최대값을 갱신해주면 됩니다. 2) 분홍색 도형 이 문제가 골드 5인 이유가 이 분홍색 도형을 따로 ..