bfs

문제 설명https://www.acmicpc.net/problem/2660 성능 요약메모리: 34088 KB, 시간: 56 ms분류너비 우선 탐색, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로제출 일자2024년 11월 14일 19:57:54문제 설명월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면..

문제 설명https://www.acmicpc.net/problem/1938 성능 요약메모리: 34216 KB, 시간: 72 ms 분류너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현 제출 일자2024년 4월 23일 00:47:02 문제 설명가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다. 다음 지형을 보자.B 0 0 1 1B 0 0 0 0B 0 0 0 01 1 0 0 0E E E 0 0위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하는 문제를 생각해 보자. BBB와 EEE의 위치는 임의로 주어진다. 단 문제에서 통나무의 길이는 항상 3이며 B의 개수와 ..

문제 설명 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 성능 요약 메모리: 34072 KB, 시간: 68 ms 분류 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색 제출 일자 2024년 4월 13일 00:46:26 문제 설명 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야..

문제 설명 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 성능 요약 메모리: 34096 KB, 시간: 524 ms 분류 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현, 시뮬레이션 제출 일자 2024년 3월 22일 02:51:49 문제 설명 N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내..

문제 설명 https://www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 문제 풀이 처음에는 치즈의 구멍을 고려하지 않고 문제를 풀었더니 당연히 실패 ... 공기가 있는 부분을 탐색하는 BFS랑, 치즈 조각을 탐색하는 BFS로 두 개의 함수를 사용하였다. 치즈 조각을 탐색하면서 근처에 공기가 한 칸이라도 있으면, set에 넣은 후 치즈가 녹는 부분들을 공기로(0으로) 만들어주었다. 그 후 공기 탐색 BFS 때 음수로 처리해주었던 공기 칸들을 다시 0으로 만들어주었다...

문제 설명 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀이 높이까지 있는 BFS문제다. dx, dy, dh로 각각 이동하는 범위를 설정하고 queue를 돌면서 확인해줬다-! from collections import deque M, N, H = list(map(int, input().split())) tomato = [[list(map(int, input().split())) for _ in range(N)] ..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 1차원 배열 bfs 문제 target이 없으면 return 0을 해주어 변환할 수 없는 경우에 시간을 줄여주었다 한 번에 한 알파벳만 바꿀 수 있다는 규칙이 있어 알파벳이 다른 개수를 구해주는 cnt 함수를 만들어주었고 달라진 알파벳이 1개이면 True를 리턴해주었다 큐를 돌아가면서 cnt 함수 return 값이 True면 현재 visited값과 이전 visited에서 1을 ..

문제 설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 풀이 이 문제는 BFS, DFS 두 방법 다 사용 가능하다 그래서 두 가지 방법으로 풀어보았다! 1. DFS 배추가 심어진 땅의 개수를 구하는 것이기 때문에 가장 먼저 DFS로 푸는 방법을 떠올렸다 재귀를 돌면서 아직 방문하지 않았으면서 값이 1인 부분을 찾고, 재귀가 끝나면 return True를 해준다 반복문으로 dfs 함수를 호출해 true면 result를 증가해준다 import sys ..

문제 설명 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 풀이 지금까지 풀었던 BFS 문제들은 2차원 리스트에서 상하좌우로 탐색하는 문제였다면 이 문제는 1차원 리스트에서 탐색하는 문제다 기존 문제들과 푸는 방법이 살짝 달라서 고민을 좀 하고 풀었다 제한사항을 읽어보고 아무 생각 없이 리스트의 크기를 100,000으로 지정했는데, 문제를 풀고 나서 코드를 다시 보니 탐색하다보면 범위를 넘을 수도 있다 수빈이와 ..

문제 설명 https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 문제 풀이 bfs를 두 번을 해야 하는 문제는 처음이라 풀이 방향을 잡는데 어려웠다 일단 불이 확산되는 시간을 구하고, 그 다음에 지훈이가 탈출할 수 있는지 확인해야 하기 때문에 BFS를 두 번 수행해야 한다 지훈이가 미로 공간을 벗어나면 미로를 탈출하는 것이기 때문에 바로 return을 해줬다 BFS는 거리 순서대로 탐색해서 무조건 최소 시간이 맨 처음에 들어오기 때문..