본문 바로가기

Algorithm/BFS

 (64)
(C++) - 백준(BOJ) 13565번 : 침투 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net bfs문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. m, n을 입력받습니다. m은 행, n은 열입니다. 2. m행 n열만큼 이차원 배열인 board변수에 적절히 입력해줍니다. 📔 풀이과정 1. 아직 전류를 흘러보낸적이 없다면 ck = 0, 있다면 ck = 1로 생각합니다. 2. 0행에 해당하는 부분은 outer side에서 전류를 흘려보낸다고 생각할 수 있..
(C++) - 백준(BOJ) 9328번 : 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 구현 + bfs문제였습니다. 📕 풀이방법 빌딩 끝에서 열쇠를 찾아 출발지점으로 돌아가 문을 열 수도 있습니다. 이 말은 왔다갔다 이동하면서 한 공간을 여러번 방문할 수 있다는 말입니다. 언제 훔친 문서를 갱신해야 하는지, 시점을 찾는 것이 중요합니다. 📔 입력 및 초기화 매 테스트 케이스마다 적절히 초기화 후 입력받습니다. 빌딩 정보를 입력 받은 후에는 열쇠 정보를 담고 있는 문자열을 입력받습니다. 이 문자열..
(C++) - 백준(BOJ) 21736번 : 헌내기는 친구가 필요해 https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net bfs문제였습니다. 풀이방법 어떤식으로 풀었는지 알고리즘 작성 1. 도연이가 한 명임이 보장되므로 입력시 'I'가 나온다면 해당 행,열 좌표를 저장합니다. 2. 도연이의 위치를 출발점으로 bfs를 수행, 한 영역에서 P의 개수를 반환합니다. Code #include using namespace std; using pii = pair; int n,m, startRow, startCol,..
(C++) - 백준(BOJ) 14923번 : 미로탈출 https://www.acmicpc.net/problem/14923 14923번: 미로 탈출 홍익이는 사악한 마법사의 꾐에 속아 N x M 미로 (Hx, Hy) 위치에 떨어졌다. 다행히도 홍익이는 마법사가 만든 미로의 탈출 위치(Ex, Ey)를 알고 있다. 하지만 미로에는 곳곳에 마법사가 설치한 벽이 www.acmicpc.net bfs문제였습니다. 풀이방법 벽 부수고 이동하기와 같은 문제였습니다. 1. bfs를 수행할 때 거리를 벽을 이미 부쉈을 때의 거리와 벽을 부수지 않았을 때의 거리를 구합니다. dist[x][y][w]로 각 상태에 따른 거리를 구할 수 있습니다. x행 ,y열의 벽의 상태 w에 대한 거리가 저장됩니다. w가 0일 때는 벽을 부수지 않은 상태, w가 1일 때는 벽을 부순상태가 됩니다...
(C++) - 백준(BOJ) 17836번 : 공주님을 구해라! https://www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net bfs문제였습니다. (첫 글자 대문자 언어 이름 ) - 문제 명 답 풀이방법 문제에서는 (1,1)에서 출발해 (n,m)에 도착하는 최소시간으로 나와있으니 (0,0)에서 출발해 (n-1, m-1)에 도착하는 최소시간으로 생각할 수 있습니다. 1. 입력을 받은 후 bfs를 두 번 수행합니다. 1-1. 첫 번째 bfs는 (0,0)에서 출발해 그람이 있는 곳으로 가는 최단시간을 구합니다...
(C++) - 프로그래머스(2021 카카오 채용연계형 인턴십) : 거리두기 확인하기 https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["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 bfs로 풀었습니다. 풀이방법 1. 모든 수험자에 대해 bfs를 수행합니다. bfs를 수행..
(C++) - 백준(BOJ) 6416번 : 트리인가? https://www.acmicpc.net/problem/6416 6416번: 트리인가? 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 한다. www.acmicpc.net 트리의 성질을 이해해 구현하는 문제였습니다. 풀이방법 입력이 트리가 1개이며 연결 그래프임이 보장되므로 다음과 같은 2가지 성질에 주의해야합니다. 1. 트리는 정점의 개수 = 간선의 개수 + 1이어야 합니다. set을 이용해 정점을 저장하고 간선은 u와 v사이의 관계를 입력할 때마다 추가함으로써 구할 수 있습니다. 2. 트리는 사이클이 없어야합니다. 즉, 한 노드에서 출발해 그 노드로 돌아오는 경로는..
(C++) - 백준(BOJ) 3055번 : 탈출 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net bfs 구현문제였습니다 풀이방법 1. '*'들 즉 물이 있는 위치를 행,열 형태로 queue에 저장합니다. 2. bfs를 통해 물이 어떤 특정 타일에 도착하는 거리들을 모두 구합니다. 3. bfs를 통해 고슴도치가 특정 타일에 도착하는 거리들을 모두 구합니다. 4. 'D'의 위치에서 인접한 상하좌우칸을 확인하며 탈출 가능여부를 판단합니다. 4-1. 탈출 경로가 존재하고 물보다 빨리 'D'의 인접칸에 도착할 수..

티스토리툴바