BFS

[LeetCode] 841. Keys and Rooms

841. Keys and Rooms Medium There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key. When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the o..

[LeetCode] 140. Word Break II

140. Word Break II Hard Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example 1: Input: s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"] Output: ["cat..

[LeetCode] 139. Word Break

139. Word Break Medium Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. Example 1: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segm..

[LeetCode] 130. Surrounded Regions

130. Surrounded Regions Medium Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example 1: Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]] Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O",..

[LeetCode] 124. Binary Tree Maximum Path Sum

124. Binary Tree Maximum Path Sum Hard A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum p..

[BOJ] 알고리즘 스터디 boj 1939 중량제한 BFS + BINARY SEARCH

이번에는 백준 1939 중량 제한을 풀어보자BFS + 이진탐색 으로 풀어야한다. https://www.acmicpc.net/problem/1939 중량제한 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB67011657101624.847%문제N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리..

[BOJ] 13565 침투 알고리즘 스터디 11월 21일

오늘 풀 문제는 침투 --> 백준에서 가져왔고 아래 주소가 있습니다. https://www.acmicpc.net/problem/13565 침투한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초512 MB165462847740.979%문제인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공..

[CodeForce] Water The Garden .A 알고리즘 스터디

알고리즘 스터디 두번째 풀어볼 문제는 아래 주소를 적어 두었습니다. http://codeforces.com/contest/920/problem/A A. Water The Gardentime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputIt is winter now, and Max decided it's about time he watered the garden.The garden can be represented as n consecutive garden beds, numbered from 1 to n. k beds contain water taps (i-th tap is loc..