상하 와 좌우를 번갈아 이동해야된다. visited 배열을 3차원으로 사용했다. 마지막은 인덱스는 가로, 세로 중 어디로 이동했냐를 가르킨다. 테스트케이스 45개만 통과되는 경우 시작점 = 도착점으로 주어져서 답이 0인 것을 처리해주지 않아서 그렇다. 예외로 0을 출력하도록 구현하면 된다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int x,y,dir; public Pos(int x,int y,int dir) { super(); this.x = x; this.y = y; this.dir=dir; } } public class Solution { static int t; static in..
www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 구현인데 어려웠다 괄호가 코딩테스트에 자주 나오는 이유 ~ 중첩된 것의 계산을 어떻게 해줄지 떠올리느냐 아니냐가 중요했다 나의 경우 괄호의 깊이를 계산해서 후위계산식으로 만들어서 계산해줄려고 했는데 너무 길고 복잡해서 다른 사람 풀이를 참고 했다. --- 중첩되어서 안쪽에 있는 괄호쌍은 앞에서 곱해온 수에 현재 괄호쌍의 값을 곱한다. 여는 괄호에서 곱해주면 된다. ( 열 때마다 중첩되서 깊어지므로) 만약 현재..
www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 처음에 네트워크를 구하는 줄알고 dfs인 줄 알았으나 depth (친구의 친구)가 2인 곳까지만 탐색하므로 bfs로 풀었다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int n,m; static ArrayList[]..
www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y; this.x = x; } } public class Main { static int n,m; static int[][] map; static in..
www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 미친 구현.. ㅎㅎ 옅은 영역과 보드가 모두 차는 경우 점수 계산 먼저하고 옅은 영역을 처리해준다. 이때 행을 밀게 되는데 옅은 영역번호 0,1 행 혹은 열에 해당하는 곳을 꼭 0으로 초기화해줘야된다. 점수를 계산할 때도 옅은 영역을 포함해서 밀어주되, 행 혹은 열이 0인 곳은 덮어씌워지지않으므로 꼭 0으로 초기화를 해줘야 된다. 나머지는 구현구현 import java.util.Scanner; pub..
www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 상어 주의할 점 사방에 냄새가 있을 경우 자기의 냄새 방향으로 간다. (자기의 냄새도 사방에 있을 수 있다. 여기서도 우선순위대로 처리해주자.) import java.util.Scanner; class Place{ int y,x; public Place(int y, int x) { super(); this.y = y; this.x = x; } } public clas..
www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 자신의 번호가 들어갈 수 있는 배열을 하나 만든다(0 초기화) 그리디 탐색으로 보고있는 자리가 비워져있다면 나보다 큰 사람이 들어갈 곳으로 판단해서 cnt를 1감소시킨다. cnt가 0이라 나보다 큰 애는 없어도 자리가 비워져있지 않다면 나보다 작은 친구가 들어간 곳이다. 다음 공간을 본다. cnt도 0이고 현재 공간이 0이면 내가 들어갈 자리이다. import java.util.Scanner; publi..
www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제자체는 어렵지 않은데 시간초과가 있어서 최적화해줘야한다. --- 풀이 r길이는 2인데 속도가 1000이라면 엄청나게 왔다갔다해야된다. 같은 위치에 있을 경우의 규칙을 찾아야된다. 주의할 점은 같은 위치에 있더라도 방향이 반대인 것은 같은 경우가 아니다! 예를 들면 C=5이고 현재 열 번호 1에 있고 우로 움직이는 상어가 있다고 하자 열 번호 1 2 3 4 5 인 경우 S=1이면 오른쪽으로..
www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 추가 설명에 비에 모두 잠기지 않을 가능성이 있다고 했다. (비가 안오는 경우가 있다. 높이 모두 1인 곳의 기준) 최대 지역의 높이 = 비의 최대 강수량으로 놓고 모든 비의 높이에 따라서 bfs를 돌려준다. 비의 높이보다 낮은 곳은 모두 0으로 만든 후 여전히 양수인 (물에 잠기지 않은 곳)의 영역을 구해준다. import java.util.LinkedList; import java.util.Queue; import..
www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net subset을 사용해서 처리해줬다. 길이가 1이상이라는 조건이 있다 import java.util.Scanner; public class Main { static int n,s; static int[] arr; static int answer; public static void main(String[] args) { Scanner sc=new Scanner(System.in)..