변을 기준으로 하는 bfs문제는 처음 풀었다. 방문 기준을 어떻게 해야할지 고민했는데 시작점과 끝점이 연결된 변을 방문 표시하기 위해서 (y,x,yy,xx)를 하나의 쌍으로 방문 배열에 넣고 같은 것이 있는지 찾았다. 만약 vis배열에 있다면 방문했던 곳이므로 answer를 증가시켜주지 않는다. function solution(dirs) { var answer = 0; let xpos=[0,0,1,-1];//DURL let ypos=[1,-1,0,0]; const dict={ 'D':0, 'U':1, 'R':2, 'L':3 }; let vis=[]; let y=5 let x=5; for(let i=0;i
1. 먼저 numbering함수에서 폭탄이 아닌 곳의 숫자를 쓴다. (for문으로 사방돌며 폭탄 몇개인지 체크, bfs필요없음) 2. 0인 곳의 처리 (bfs) 0인 곳은 연속으로 터지므로 큐에 0을 넣고 돌려 폭탄이 아닌 곳을 모두 폭탄(-1)로 바꿔준다. -1로 바꿔주는 것은 방문표시임과 동시에 더이상 터트릴 필요가 없어지는 숫자라고 생각하면 된다. 0의 개수만큼 cnt를 1증가시켜준다. 3. 1이상 숫자인 곳의 처리 마지막 배열 이중 포문을 돌면서 1이상의 숫자들은 일일히 눌러줘야하므로 만날때마다 cnt를 1증가시켜준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Sc..
www.acmicpc.net/problem/5525 5525번: IOIOI 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. (1 ≤ N ≤ 1,000,000, 2N+1 ≤ M ≤ 1,000,000) www.acmicpc.net import java.util.Scanner; public class Main { static int n,m; static String s; public static void main(String[] args) { Scanner sc=new Scanner(System.in); n=sc.nextInt(); m=sc.nextInt();//s의 길이 s=sc.next(); StringBuilder sb=new StringBuilder(); f..
www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 반례 3 3 => 0 1 2 3 2 => 1 2 5050 99 => 1부터 100까지 10 4 => 1 2 3 4 10 5 =>0 1 2 3 4 5 슬라이딩 윈도우처럼 앞에서부터 더해가며 n보다 커지면 가장 앞의 수를 빼주면 되는 문제이다. 더해준 수의 시작점과 끝점을 구해줘야 되는데 끝점은 현재 인덱스 i이고 시작점은 초기 0으로 둔 다음에 수가 커서 빼줄 때마다 1씩 더해준다. 길이가 l이상일 때 import java.util.Scanner; pu..
a라는 사람과 b사람이 벌꿀을 채취하는데 벌집이 중복되지 않도록 해야된다. a라는 사람은 모든 행, 열 기준으로 고르는데 b라는 사람은 a와 같은 행이라면 열이 중복되지 않도록 해야하고 다른 행이면 상관없이 뽑는다. 1. collect 함수 a는 모든 경우를 전사적으로 구해주므로 list에 집어넣는다. (추후 다른 행이면서 열이 중복된 경우를 계산할 때 쓴다) b는 a와 행이 겹치지 않는 부분에서 subset을 돌려준다. 일단 이 함수에서 a의 최대값과 b의 최대값의 합의 최대값으로 answer를 갱신해주면 행은 같은 경우는 끝난다. 2. calculate함수 다른 행의 중복된 열을 구해준다. a라는 사람은 collect함수에서 전사적으로 모든 subset 경우를 구해줬다. a사람이 구한 리스트지만 이제..
처음에 플로이드 와샬로 풀었는데 t의 자리에 tc를 넣었다가 런타임에러 났었다. 내일 다시 플로이드 와샬로 풀어봐야지 내 위치에서 dfs로 돌면서 next(나보다 큰 친구들)의 count값을 증가시키면 next입장에서는 작은 애들의 개수만큼 업데이트가 된다. temp는 dfs를 도는 횟수를 가르키는데 현재 내 번호보다 큰 친구들의 수(나 포함)로 count[내번호]+temp 해주면 나보다 큰 친구들의 수를 구할 수 있다. 이렇게 temp로 업데이트 (나 포함해서 나보다 큰 친구들의 수) + count[next] 업데이트 (나보다 작은 친구수만큼 증가) 의 합이 n이 되면 나의 순서를 알 수 있는 경우이다. import java.util.ArrayList; import java.util.Scanner; p..
www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 최대 길이가 100만 가능하므로 미리 크기 100으로 만들어놓고 넘어가는 길이의 데이터만 무시해준다. 각 행별로 각 수를 count배열에 등장하는 만큼 1로 더해줘서 (수, 등장횟수) 쌍을 리스트에 넣어준다. 리스트에 넣어줄 때 중복된 수가 들어가지않도록 주의! 해준다 리스트를 기준에 따라 정렬한다. 최대 행 길이와 최대 열 길이는 정렬할 때마다 새로 구해줘야된다. 계속 max연산만 하면 이전 정렬..
www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 프로그래머스에도 있는 문제다 일단 리스트에 트럭을 입력받는다는 생각에 list로 했지만 arraylist대신 queue를 쓰면 시간 효율성에 더 좋을 것이다 다리에 들어가는 트럭 리스트: Queue q 다리에 들어가려고 기다리는 리스트: list q혹은 list의 길이가 아직 1이 아니면 진행이 종료되지 않은 트럭이 있으므로 기다린다. 트럭이 빠져나오는 시간은 현..
www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 2번 감시카메라 방향 종류는 위아래 검사, 좌우 검사 2가지이고 5번 감시카메라는 1가지 이다. (사방을 검사하기 때문에) 나머지 감시카메라의 방향 종류는 4가지이다. (90도 회전할 때마다 검사하는 곳이 달라진다) 나는 위를 검사할 때를 0 , 오른쪽 1, 아래쪽 2, 왼쪽을 3으로 인덱스를 둬서 각각 해당방향으로 cctv가 닿는 곳을 검색하는 함수를 따로 구현했다. mark이차배열을 둬서 해당 위..
www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 골드 1,2 풀다가 실버 푸니까 더 헷갈리는 것 같다 for문을 돌면서 . 인곳을 O를 표시해주고 터트릴 시간을 적어준다. 큐 없이 풀 수 있는 문제 for문으로 돌면서 체크해놓은 터트리는 시간과 같은 곳을 다시 .으로 만들어준다. package algo0421; import java.util.Scanner; class Pos{ int y,x; public Pos(int y, int x) { super(); this.y = y;..