C++
-
백준(BOJ) 알고스팟알고리즘 풀이/백준(Boj) 2020. 3. 16. 20:26
문제 : https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 풀이 : 우선 행 열이 아니고 열 행으로 주어지는 n, m에 주의하자. 0,0부터 시작해서 n-1 m-1로 가는 것은 priority queue를 통해서 가장 적게 벽을 부순 좌표가 먼저 나올 수 있도록 해주었다. 마이너스를 붙여서 따로 greater 처리를 하지 않고 오름차순 처리를 해주었다. 코드 ( C++ )
-
백준(BOJ) 16929번 Two Dots알고리즘 풀이/백준(Boj) 2020. 3. 13. 16:42
문제 :https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다. www.acmicpc.net 풀이 : DFS를 통해 사이클이 발견 시 true를 반환하도록 ccheck 함수를 만들었다. 이때 by bx는 이전 y,x를 나타내는데 if (ny == by && nx == bx )는 뛰어넘도록 만들어 주었다. by와 bx가 없다면 오른쪽으로 갔다가 바로 왼쪽으로 가는 경우도 사이클로 판단하기 때문이다 코드 ( C++ )
-
백준(BOJ) 16986번 인싸들의 가위바위보알고리즘 풀이/백준(Boj) 2020. 3. 13. 15:34
문제 : https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되어있기 때문에 이전 라운드의 결과와 무관하게 지우와 경희가 같은 손동작을 냈으면 경희의 승리이고, 지우와 민호가 같은 손동작을 냈으면 민호의 승리이고, 경희와 민호가 같은 손동작을 냈으면 민호의 승리이다. 비둘기집의 원리에 의해 3(K-1)+1번의 경기를 치르면 누군가 www.acmicpc.net 풀이 : 처음 p1은 0 p2는 1로 시작한다. 나머지 사람은 3 - p1 - p2로 구할 수 있다. 지수의 가위..
-
백준(BOJ) 1194번 달이 차오른다, 가자.알고리즘 풀이/백준(Boj) 2020. 3. 12. 00:58
문제 : https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, 영식이가 열쇠를 숨겨놓는 다면 문에 대응하는 열쇠가 없을 수도 있다. 0은 한 개, 1은 적어도 한 개 있다. 그리고, 열쇠는 여러 번 사용할 수 있다. www.acmicpc.net 풀이 : BFS문제이고 비트 마스킹으로 푼다면 쉽게 풀 수 있는 문제였습니다. 1
-
백준(BOJ) 2002번 추월알고리즘 풀이/백준(Boj) 2020. 3. 9. 17:00
문제 : https://www.acmicpc.net/problem/2002 2002번: 추월 문제 대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다. 소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차 www.acmicpc.net 풀이 : 해쉬 맵을 통해 각 차량이 들어온 번호와 순서를 적어두자 이제 나온 번호를 보면서 해당 차량에..
-
백준(BOJ) 1175번 배달알고리즘 풀이/백준(Boj) 2020. 3. 8. 04:16
문제 : https://www.acmicpc.net/problem/1175 1175번: 배달 어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다. 입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다. S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다. C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하 www.acmicpc.net 풀이 : BFS를 통해 최소 거리를 구해주었는데 이때 d는 4차원으로 잡았다. 그 이유는 4가지 방향 배열에 의해서 각각의 경우가 ..
-
백준(BOJ) 17406번 배열 돌리기 4알고리즘 풀이/백준(Boj) 2020. 2. 22. 17:06
문제 : https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net 풀이 : 순서는 임의로 정해도 된다. 는 글을 놓쳐서 몇 번 실패하였던 문제이다. order는 0,1,2,3 .. k..
-
백준(BOJ) 17281번 ⚾알고리즘 풀이/백준(Boj) 2020. 2. 20. 02:29
문제 : https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 www.acmicpc.net 풀이 : 첫 주자인 0번은 무조건 4번째에 들어가기 때문에 1~8까지 next_permutation을 통해 순서를 돌려주고 solv..