자바

[JAVA/자바 백준 17472] 다리 만들기2

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 bfs , prim 알고리즘을 사용했습니다. 1. bfs를 사용해서 섬들을 구분 지어줬습니다. 섬 2번부터 시작해서 2,3,4,5 2. 다리를 지을 수 있는 상황이면 모두 지어주고 거리에 따라 오름차순으로 정렬되게 edgeList에 넣어줬습니다. 3. prim 알고리즘을 사용하여 최소 스패닝 트리를 만들었습니다. 반례) 1. ㄷ자형 섬에 대하여 처리를 해줬습니다. 2. ..

[JAVA/자바 백준 14502] 연구소

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 dfs, bfs 문제입니다. 저는 우선 bfs로 풀었습니다. 1. make_wall 함수를 만들어서 3개의 벽을 만들어주는 기능(combination)을 구현하구, 2. 조건을 만족하면 bfs 탐색을 했습니다. --막힌 점 조합을 써야하는건 알았지만 2차원 배열에서 구현하는데 조금 시간어 걸렸습니다. import java.io.*; import java.util.*; // bfs문제 // 벽을 만들 수 ..

[JAVA/자바 백준 1149] RGB거리

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 1. 2차원 배열 Cost에 우선 해당하는 rgb에 비용 값을 모두 넣어줍니당. 2. Cost[i][0](red) 일 경우 Cost[i][1](green) Cost[i][2](blue) 중 최솟값을 더해줍니다. 0(Red) 1(Green) 2(Blue) Cost[0][0] Cost[0][1] Cost[0][2] Cost[1][0] += Min(Cost[0][1],Cost..

[JAVA/자바 10026 백준] 적록색약

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 풀이 일반적인 bfs 문제 bfs 함수 부분을 한번만 쓰려고 적록색약 아닐때 version=true, 적록색약 일때 version=false로 나눠주고 적록색약인 경우 R과 G를 같은걸로 보니까 R일경우 G를 봐도 큐에 넣어주고 G일경우 R을 봐도 큐에 넣어주고, check 값을 true로 바꿔줬습니다. import java.io.*; import java.util.*; class xy{ ..

[Java SWEA 1247] 최적 경로

풀이 순열을 이용해서 풀었습니다. 문제에서도 전부다 순회하면 풀수있다고해서, 완전탐색 써야겠다구 생각했습니다. 순열을 사용해서 numbers배열에 customer_arr 인덱스 값을 넣었습니다. sum()내에서는 현재의 x,y값을 계속 바꿔가면서 거리계산을 했습니다. package a0819; import java.io.*; import java.util.*; class customer{ int x; int y; public customer(int x, int y) { this.x = x; this.y = y; } } public class Main { static int home_x,home_y,current_x,current_y,company_x,company_y, n; //customer 좌표 위치..

[JAVA/자바 1992 백준] 쿼드트리

https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 find 부분이 중요합니다. 다른분들은 파라미터 3개로 쓴 사람도 있는데, 풀다가 헷갈려서 5개로 나눠서 썼습니다. 분할정복 문제이므로, label을 처음 사용해서 해결 가능한 문제인지 판단하고, 할수없으면 break 한뒤 1,2,3,4분면으로 나눠서 재귀적으로 돌립니다. 가능하다면 flag 불린값을 바꿔주고, stat~end까지 출력해줍니다. import java.awt.Lab..

[JAVA SWEA 1210 ] Ladder1

풀이 arr에 값을 모두 넣어주고 find에 도착점인 x,y, arr를 넘겨주었습니다. find내에서 방향 dir을 정해주고, dir이 좌 방향일때와 우방향일땐 상 방향 먼저 탐색하고 자기 자신 방향을 탐색하게끔, 상 방향일땐 자기 자신 방향 먼저 탐색하게끔 했습니다. import java.io.FileInputStream; import java.io.*; import java.lang.*; import java.util.StringTokenizer; public class Solution { // 좌 상 우 static int[] dx ={0,-1,0}; static int[] dy= {-1,0,1}; //출발점 찾기! static void find(int x, int y, int[][] arr) { ..

[Python/파이썬, Java/자바 백준 7576] 토마토(BFS)

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 시간초과에 주의해서 표를 입력받을때 1이면 바로 큐에 넣어줬습니다. 이렇게 되면 첫째날 bfs를 할 토마토만 큐 안에 있고, 일자별로 같은 날 들어온 토마토만 bfs 돌리기 위해서 for문에 큐 길이만큼만 돌려주었습니다. 이렇게되면 첫째날 들어온 토마토만큼만 bfs 돌고 result +1 둘째날 들어온 토마토만큼만 bfs 돌고 result+1 . . 이런식으로 탐색하여 result를 리턴시..