www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 청소년 상어를 풀고나서 이 문제를 푸니 dfs가 익숙해서 dfs로 경우를 탐색하다가 메모리 초과가 났다. 가끔 bfs로만 되거나 dfs만 되는 문제들이 있어서 헷갈리는데 최단 시간 (같은 위치 구간에서 동시에 탐색할 때)는 bfs이고 모든 경우의 수를 다 돌아봐야하는 경우 (청소년 상어처럼 먹는 물고기 번호가 가장 큰것을 구하는 것)은 dfs인 것 같다. 물이 차오를 지역도 못간다는 것은 즉, 물이 찬 것과 같다라는 뜻이라..
www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 물고기 이동은 구현에서 상어이동은 dfs로 완탐을 돌려줘야되는 문제여서 복잡했다 ㅠㅠ 지쳐.. 중간에 상어가 멈춰서 ?? 했는데 나는 상어이동을 bfs로 구현했고 물고기가 있는 칸으로만 이동하는 것으로 짰더니 빈 칸으로는 이동을 못해 오도가도 못한 상태로 끝나버렸다. 추후 빈 칸도 갈 수 있도록 했더니 통과되었다. 칸이 4x4로 정해져있기 때문에 무조건 3번 이동이 가능한지 for문으로 확인하..
www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net arraylist는 검사 시작점과 연합국인 곳들의 좌표가 들어가는 리스트이다. 1. 방문 안된 곳에서 상하좌우를 검사하면서 경계를 열 수있는 곳을 검사한다. 연합국이 되면 sum+=연합국 인구수, cnt(연합국에 들어가는 개수)+1해주고 arraylist에 새로운 연합국의 좌표를 넣어준다. 2. 시작한 곳에서 bfs로 최대한 검사할 수 있는 곳까지 다 검사가 끝나면 arraylist 좌표에 해당하..
푸는 데 소요시간: 40분 파이프 방향이 위일때는 다음 칸의 파이프가 방향 아래를 포함하고 있으면 된다. 이처럼 다음 칸의 방향이 내 방향의 반대인 숫자를 가지고 있나 체크해주면 된다. import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y,x,type; public Pos(int y, int x,int type) { super(); this.y = y; this.x = x; this.type=type; } } public class Solution { static int t,m,n,l; static int[][] map; static int[]..
www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net bfs로 뭐든 되는구나 싶었다 1번이랑 n번이 연결된다는게 뭔가 싶었는데 범위를 넘어가면 그만큼 빼서 다시 안의 범위로 들어오게 해야된다 그 다음에는 파이어 볼 개수만큼 큐에 집어넣고 그 길이만큼만 bfs로 돌린 후 다시 새로 만든 파이어볼을 큐에 넣고 k번 돌리면 된다. import java.util.ArrayList; import java.util.LinkedList;..
bfs 심화랄까 벽돌을 n번 깨뜨릴 수 있는데 열의 길이 w 중에 어디를 n번 때릴지 미리 결정한 후 (중복조합) 그 다음에 bfs 돌린다고 생각해놓고 짜면 훨씬 낫다. 백준 토마토 문제처럼 연속적으로 깨지게 되는 벽돌을 모두 처리한 후 다음 bfs를 돌린다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int y; int x; int num; public Pos(int y, int x, int num) { super(); this.y = y; this.x = x; this.num = num; } } public class Solution ..
www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 앞뒤를 나타내는 좌표 이동을 추가해서 추가로 검사해준다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Pos{ int h,y,x; public Pos(int h, int y, int x) { super(); this.h = h; this.y = y; this.x = x; } } pu..
www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 한 번에 1인 곳 주변이 모두 익어야되기 때문에 큐에 현재 1인곳을 다 집어넣고 매번 순회할 시에 모두 bfs탐색을 한꺼번에 해준다. for문 (현재 익어있는 토마토 개수)만큼 bfs를 돌면서 큐에 넣어준 다음에야 다음 차례의 토마토들이 큐에서 나온다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; c..
set을 이용해서 문자열이 중복으로 들어가지 않도록 한 후 최종 set의 길이를 출력해주었다. import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; class Item{ int y,x; String result; public Item(int y, int x, String result) { super(); this.y = y; this.x = x; this.result = result; } } public class Solution { static int t; static int[][] map; static int[] xpos= {0,..
1. java import java.util.Arrays; 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 Solution { static int t,n; static int[][] map; static int[] xpos= {1,-1,0,0}; static int[] ypos= {0,0,1,-1}; static int[][] vis; public static void main(String[] args) { Scanner sc=new Scan..