BFS

[Java/자바 swea 5653] 줄기세포배양

풀이 조건 1. map의 크기 map은 무한대로 크다고 하였으니 K에 따라서 여유있게 잡아줘야합니다. 2. 생명력이 높은순으로 같은 시간에 두개의 세포가 같은 곳에 퍼져나가는 경우가 있습니다. pq를 사용해서 생명력이 높은 순서대로 꺼내주도록 합니다. 3. 시간별로 진행. 시간별로 진행하므로,, pq랑 별개로 temp 큐를 만들어서 pq에서 temp로 넣어주고 pq가 비게되면 temp에서 다시 pq로 넣어줍니다. 4. 활성화 비활성화. 생명력 크기만큼 시간이 지나야 활성화가 되고, 또다시 생명력 크기만큼 시간이 지나면 죽으므로 현재 curLife를 2배로 지정해서. original이 크면 활성화를 시작하구 curlife가 0이 된다면 큐에 넣어주지 않습니다. import java.io.*; import ..

[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/자바 백준 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문제 // 벽을 만들 수 ..

[Python/파이썬 백준 13913] 숨바꼭질 4 (BFS)

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 다른 숨바꼭질 문제랑 같지만 path를 하나 더 써줘서 nx 인덱스에 전에 방문했던 x를 넣어줬습니다. 그 뒤 path[end]에 값을 따라가다보면 start가 나오게됩니다. import sys from collections import deque input=sys.stdin.readline start,end=map(int,input().split()) graph=[-1]..

[Python/파이썬 13549 백준] 숨바꼭질 3

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 bfs문제입니다. 2*x, x-1, x+1인 경우에서 2*x 인 경우 : 순간이동하므로 시간 +0, appendleft해서 가장 우선순위로 설정하여 1000001까지 최단시간 미리 구해줌 x-1,x+1인 경우 : +1씩 더해줌 풀면서 시간초과 났었는데 apppendleft를 안써주고 if문으로 하나하나씩 정의해줘서 시간초과났음... import sys from collec..

[Python/파이썬 3055 백준] 탈출

www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 bfs 문제인데 물의 경로가 고슴도치에 영향을 주는 문제 처음 물(*)을 bfs 돌려서 check_water에 시간을 넣어줬습니다. 이 과정에서 물이 여러 개인 경우랑 두번째 물 bfs 일 경우 시간이 더 적게 걸리는 상황으로 걸러줬습니다. 다음 고슴도치(S) bfs 돌려서 물이 아예 없을 경우와 물보다 빨리 고슴도치가 움직인 경우를 걸러줬습니다. 제출과정에서 계속 10%에서 불통됐는데 반례가 D.. ... ..S 이..

[Python/파이썬 백준 13460] 구슬탈출2 (BFS)

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬 탈출 2 분류 시간 제한메모리 제한제출정답맞은 사람정답 비율 2 초 512 MB 45509 13190 6937 25.692% 문제 스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다. 보드의 세로 크기는 N,..

[Python/파이썬 백준 2468] 안전 영역(BFS)

www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 check 해주는 그래프를 3중 리스트로 사용했는데 z 범위를 가장 큰 높이로 받아서 3중 리스트를 선언해주었습니다. z를 0~height-1 까지 범위를 잡아서 BFS를 돌렸는데 z범위가 엄청 헷갈렸...(0을 포함 안하고 돌렸었는데 틀렸다해서 넣었더니 성공... 안내릴 경우도 포함해주는건가...) cnt로 안전 영역을 세주고 최대 영역 값을 max로 판단했더니 성공~ #안전 영역 # z를 0~ 제일 큰 높이까..

[Python/파이썬 백준 5104] 스타트링크(BFS)

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 일차원 BFS 문제입니다. S,G 를 start, end값으로 선언했으며 U,D 을 dx 값에 +U 와 , -D 를 넣어줬습니다 check 값을 비교해서 queue에 삽입되면 +1씩 시켜줬으며 check[end]를 반환시켜줘서 출력시켰어용~~ # 스타트링크 # 일차원 BFS 문제이며, U,D 을 nx 값에 넣어줘서 # check 해당 값 출력 from collections import deque import sys i..

[Python/파이썬 백준 1012] 유기농 배추(BFS)

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 #배추 벌레 문제 bfs 돌때마다 증가 시켜주면 되는데 x,y 신경잘써서 from collections import deque import sys input=sys.stdin.readline T=int(input()) dx=[1,-1,0,0] dy=[0,0,-1,1] for i in range(T): m,n,k=map(int,input().split()) graph=[[0]*m for _ in range(n)] che..