본문 바로가기

BFS8

BOJ 23289 - 온풍기 안녕(Java) https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 풀이 조사하는 칸(배열 입력 칸이 5인 칸)이 모두 K 이상일 때까지 1~3 반복후, 초콜릿의 갯수를 출력 1. 모든 온풍기에서 바람이 나옴 온풍기의 방향에 따라 온도가 확산 하나의 좌표에서 온풍기의 방향에 따라 3방향으로 확산 중첩되는 좌표의 경우 한번만 계산 2. 온도 조절 상하좌우 인접한 칸을 조사, 온도가 높은 칸은 온도를 줄이고 낮은 칸은 온도를 높임 이는 모든 칸에서 한번에 실행됨 3... 2022. 1. 12.
BOJ 20058 - 마법사 상어와 파이어 스톰(Java) https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 풀이 1. 명령의 수 만큼 반복, 명령 L에 대해 진행 1) 2L X 2L로 구역 나누기, 구역 별 회전 2) 인근 지역에 얼음이 없다면 얼음줄이기 - 동서남북 4방향에 대해 얼음이 남은 인접 칸의 개수 확인 - 인접 칸의 개수가 3이상이 아니라면 해당 칸의 얼음을 1 줄임 2. 1이 끝나면 남아있는 얼음의 합, 전체 영역 중 가장 큰 덩어리를 탐색 명령 L에 따른 구역 나누기.. 2022. 1. 8.
BOJ 16985 - Maaaaaaaaaze(Java) https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이 1. 2가지를 기준으로 모든 경우의 수를 탐색 1) 판의 회전(어느 판을 얼만큼 회전할지) 2) 회전을 완료한 5개의 판 쌓기 2. 위의 기준으로 만든 3차원 행렬을 bfs 거리 탐색 몇번째 판이 몇도 회전하는지 각 판마다 몇 도 회전하는지 모든 경우의 수를 탐색 - 현재 판을 90도 회전 시키고 다음 판에 대해 재귀 호출 5번째(마지막)판에 대한 결정이 끝나면 판을 쌓.. 2022. 1. 6.
BOJ 16234 - 인구 이동(Java) https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 인구이동이 더 이상 불가능 할때 까지 계속해서 이동 반복 이동되는 구역을 visit[][]로 확인, 다시 탐색하지 않도록 예외 처리 - 인구 이동이 가능한지 확인 - 인구 이동이 가능하다면 해당 구역 전체 인구 이동 - bfs를 이용하여 인근 구역 탐색 -> L < abs( map[y][x]-map[ny][nx] ) < R이라면 이동 가능 - 인구이동 구역 설정까지 bfs 탐색.. 2021. 12. 14.
Programmers - 카카오프렌즈 컬러링북(JAVA) https://programmers.co.kr/learn/courses/30/lessons/1829?language=java 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이 * 0은 색칠하지 않은 영역, 영역 탐색 대상에서 제외 1. 이차원 배열 각 요소마다 탐색 - 이미 탐색했거나(visit[y][x]==true) 해당 위치의 값이 0이면 continue - 외의 경우에는 현재 위치가 이전까지 찾은 영역과 다른 새로운 영역이기 때문에 영역 갯수+1, 영역 사이즈 구하기(2로 이동) 2. 상하좌우 인접한 .. 2021. 12. 3.
BOJ 23288 - 주사위 굴리기2(C++) https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 풀이 주사위 배열에 주사위 위치의 값 저장, 주사위 이동 시 배열 갱신 이동방향 dir[]={동, 남, 서, 북} 반복횟수 K만큼 진행 1. 주사위가 이동 방향으로 한칸 굴러감(굴러간 위치가 범위 밖이라면 반대방향으로 계산) - 주사위의 이동방향에 따라 주사위 배열의 값 수정 2. 주사위의 위치 (y, x)에 대해 점수 계산 - 동서남북 방향으로 연속해서 이동할 수 있는(BFS).. 2021. 11. 25.
Programmers - 퍼즐 조각 채우기(C++) ≠https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차_퍼즐 조각 채우기 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 풀이 각 조각간의 비교만 하면 됨 1. 퍼즐과 빈 공간 나누기(BFS), 위치 정보 변환 ex 2. 각 조각 비교 2-1... 2021. 9. 24.
BOJ 17142 - 연구소3(C++) https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 0. 입력데이터에서 바이러스의 위치, 2번의 완료조건(바이러스가 퍼져야하는 방의 수)를 저장 1. 입력 데이터의 바이러스 중 M개의 바이러스를 활성화 - 모든 바이러스중 M개를 선택하여 모든 경우의 수에 대해 시뮬레이션(브루트포스) 2. 활성 상태의 바이러스는 상하좌우로 전파되며 모든 빈칸에 바이러스가 퍼지는 최소 시간을 구함 - 1에 대한 모든 경우의 수에 bfs를 이용하여 바이러스가 퍼지는 시간을.. 2021. 8. 25.

티스토리툴바