본문 바로가기

bfs16

[백준] 21609 상어 중학교 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 문제의 설명이 굉장히 긴 편이라 위 링크의 문제를 꼼꼼히 읽어보시고 풀이과정을 살펴보시길 추천드립니다. 일반적인 BFS/ DFS 문제보다 신경써서 구현해야 할 부분들이 훨씬 까다로운 문제이므로 과정을 하나하나 잘 살펴보면서 구현하시는 것을 추천드립니다. 풀이 과정 먼저 두 방법으로 풀면서 코드를 두 가지로 작성해보았습니다. 코드①은 구현해야 할 부분들을 그대로 나열식으로 작성한 코드.. 2021. 10. 22.
[백준] 14502 연구소 (Python 파이썬) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 N x M 크기로 구성된 연구소에 바이러스가 퍼졌다. 연구소의 각 칸은 0, 1, 2로 구성되어 있으며 0은 빈 칸, 1은 벽, 2은 바이러스 이다. 바이러스는 벽을 뚫고 확장할 수 없으며 상하좌우에 인접한 빈 칸으로만 확장이 가능하다. 위 그림과 같이 N x M 모양의 연구소(행렬)가 주어지며, 3개의 벽(1)을 세워야 한다. 3개의 벽을 세웠을 때, 안전영역의 크기(0의 개수)의 최댓값을 구하면.. 2021. 10. 17.
[백준] 13460 구슬 탈출2 (Python 파이썬) https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 설명 위의 문제의 그림처럼 N * M 의 보드가 주어졌을 때, 빨간색 구슬을 구멍안에 넣는 게임이다. 파란색 구슬이 구멍안에 들어가서도 안되고, 굴리는 횟수가 10번을 넘어가서도 안된다. 여러가지 제약조건들이 많은 까다로운 BFS 문제이다. 풀이 과정 구슬을 굴리게 되면, 벽이나 구멍에 닿을 때 까지 구슬은 계속 굴러간다. 따라서, 방향 하나.. 2021. 10. 14.
[프로그래머스] 거리두기 확인하기 (Python 파이썬) https://programmers.co.kr/learn/courses/30/lessons/81302#fn1 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 문제 설명 대기실 상태가 그래프(배열)로 주어진다. 응시자 간 간격이 맨하튼 거리 .. 2021. 10. 9.
[백준] 1012 유기농 배추 (Python 파이썬) www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 설명 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추.. 2021. 5. 8.
[백준] 2667 단지번호붙이기 (Python 파이썬) www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 설명 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단.. 2021. 5. 8.

티스토리툴바