분류 전체보기

[Java/자바 swea 4013] 특이한 자석

풀이 처음 스택을 쓰려고 했는데 엄청 복잡했습니다... 그래서 2차원 배열을 통해 구현했습니다. map 4x8 2차원 형태로 저장하구 , arr에 시계면 1, 반시계면 -1, 회전 하지않는다면 0 으로 담았습니다. 받은 인덱스 값을 바탕으로 왼쪽,오른쪽을 나눈 뒤 오른쪽일 땐, map[idx][6]번과 map[idx-1][2] 을 비교해준 뒤 값을 arr 를 넣어주고 왼쪽도 비슷한 로직으로 arr 넣어줍니다. arr를 기준으로 시계,반시계로 돌려줍니다 시계방향은 끝에 있는 값을 처음으로 넣어줍니다. 반시계방향은 처음 값을 마지막으로 넣어줍니다. 풀이 완료!! import java.io.*; import java.util.*; public class Solution { static int[][] map; ..

[Java/자바 swea 1868] 파핑파핑 지뢰찾기

풀이 우선 map에 character 형식으로 담아준 뒤, 팔방탐색을 통해 지뢰의 개수를 넣어줬습니다. 지뢰의 개수가 0 일때가 핵심 !! map[i][j]=0 일때 주변의 0들을 탐색하며 붙어있는 0들도 같이 한번의 탐색하며 방문 처리를 합니다 . 0인것들을 전부 다 방문처리를 한 후 다시 반복문을 통해서 방문하지 않은 것들의 개수를 세주면 풀이 완료! import java.io.*; import java.util.*; public class Solution{ static char[][] map; static boolean[][] visited; static int[] dx = {0,1,0,-1, 1,1,-1,-1}; static int[] dy = {1,0,-1,0, 1,-1,1,-1}; static..

[Java/자바 swea 5643] 키 순서

풀이 나보다 작은 사람들과 큰 사람들의 리스트를 만들어주었습니다. 큐를 이용해서 작은 사람들을 찾아가는 로직을 구현했고 나보다 작은 사람들 중 방문하지 않았다면 큐에 bfs를 이용했습니다. import java.io.*; import java.util.*; class Edge{ int height; public Edge(int height) { super(); this.height = height; } } class Solution { static Queue q_small=new LinkedList(); static Queue q_big=new LinkedList(); public static void main(String[] args)throws Exception { // TODO Auto-genera..

[Java/자바 swea 8458] 원점으로 집합

풀이 1) 좌표와 원점까리 거리 중 홀수는 홀수끼리, 짝수는 짝수끼리 존재해야 같이 도달할 수 있습니다. 좌표들 중 거리가 짝수랑 홀수가 섞여 있으면 정답 x 2) max값이 원점에 도달하는 거리를 계산해야합니다. max%2 == sum%2 과 sum>= max보다 크거나 같은지 조건을 따져주면서 sum을 1,2,3,4, 씩 더해주면서 값을 구해야합니다. 수학문제는 어렵네요 ㅜㅜ import java.io.*; import java.util.*; class Solution { public static void main(String[] args)throws Exception{ // TODO Auto-generated method stub BufferedReader br= new BufferedReader(..

[Java/자바 백준 4485] 녹색 옷 입은 애가 젤다지?

풀이 최단 경로를 묻는 bfs 문제입니다 map에는 루피값을 넣어주고 check에 해당 경로까지 최솟값을 갱신해주면서 bfs를 풀었습니다. 아래처럼 방문한 적이 있든 없든, check에 해당 경로까지 최솟 값이 있으므로 조건을 줘서 다음경로까지의 거리합 > 현재 경로까지의 거리합 + 다음 경로 거리값 이면 큐에 넣어줬습니다. if(check[nx][ny]>check[x][y]+map[nx][ny]) { check[nx][ny]=check[x][y]+map[nx][ny]; queue.offer(new int[] {nx,ny}); } import java.io.*; import java.util.*; // bfs문제 check 현재 위치를 도달할 수 있는 최솟값을 갱신하면서 탐색 public class Ma..

[JAVA/자바 정올 1681] 해밀턴 순환회로

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL www.jungol.co.kr 풀이 백트래킹, 순열 문제입니다. 회사에서 출발해서 배달 장소들의 순열을 돌고 다시 회사로 도착하므로 0 -> 배달지의 순열 -> 0 ( 문제 설명에서는 1을 회사라 소개하지만 코드상 0이 회사입니다) 이런식으로 구현해서 풀었지만 시간초과가 났습니다. 이후 백트래킹 기법을 추가했습니다. permutation 함수에서 파라미터를 val을 받아서 현재의 배달 비용을 저장하고, min_val(조건에 부합하는 최솟값)과 비교를 해줘서 val 크다면 다음 순열로 백트래킹. import java.io.*; import java.util.*; public..

[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/자바 SWEA 3124] 최소 스패닝 트리

풀이 * Kruskal 알고리즘 - 인접 리스트 사용 import java.io.*; import java.util.*; //Kruskal // 정점과 간선이 크므로 edgelist로 풀어아야함 // 가중치 값이 1,000,000이 누적되면 int 범위 넘으므로, result를 long 타입 public class Solution{ static int[] parents; static int V,E; static Edge[] edgeList; static class Edge implements Comparable{ int start,end,weight; public Edge(int start, int end, int weight) { super(); this.start = start; this.end = ..

[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..