본문 바로가기

bfs

[백준] 15658 연산자 끼워넣기 2 (Python 파이썬) www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수 www.acmicpc.net 문제 설명 주어진 숫자와 연산자로 만들 수 있는 수식의 결과값 중 최대값과 최소값을 구하면 됩니다. 풀이 과정 DFS의 백트래킹을 이용해서 풀어도 되고, 아래의 코드처럼 변수로 변하는 변수를 넘겨주어도 됩니다. 핵심은 주어진 숫자와 연산자로 조합할 수 있는 모든 경우의 수를 따져야 합니다. 백트래킹을 이용한 코드는 https://hongcoding.tistory.com.. 더보기
[프로그래머스] 단어 변환 ( Python 파이썬 ) programmers.co.kr/learn/courses/30/lessons/43163# 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설명 두개의 단어 begin과 target이 주어지며 단어의 집합 words가 주어집니다. begin은 words에 있는 단어 중 하나로 변경 가능하며, 한 번에 하나의 알파벳만 변경가능합니다. 이러한 과정을 통해 target까지 가는데 몇 단계의 과정을 거쳐야 하는지를 출력하면 됩니다. 문제의 자세한 설명은 위 링크에 나와있.. 더보기
[백준] 1707 이분그래프 (Python 파이썬) www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 설명 문제에서 말한 이분그래프란, 그래프 정점의 집합을 둘로 나눴을 때, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있는 그래프를 말한다. 즉, 그래프의 정점을 두가지 색으로 칠할 때, 인접한 정점끼리는 다른 색을 가지고 있는 그래프 인 것이다. 위 그림은 대표적인 이분그래프이다. 풀이 과정 visited[V]에 1, 2의 값을 줌으로써 정점의 색을 구분한다. ( 단, 아직 미.. 더보기
[백준] 7562 나이트의 이동 (Python 파이썬) 문제 설명 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 체스판 위의 나이트가 최소 몇번을 움직여 도착지까지 이동할 수 있는지를 구하는 문제이다. 풀이 과정 나이트가 이동할 수 있는 경로는 체스의 나이트와 똑같이 가로2칸 이동후 세로1칸 혹은 가로1칸 이동 후 세로1칸 이기 때문에 8가지 상황이 발생한다. visited의 각 칸에는 그 칸까지 오는데 필요한 횟수가 저장되어 있으며 초기는 모두 0으로 저장되어 있다. 즉, 아직 밟지않은 칸은 모두 0으로 초기화.. 더보기
[백준] 2206 벽 부수고 이동하기 (Python 파이썬) 문제 설명 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net N×M의 행렬로 표현되는 맵에서 0은 이동할 수 있는칸, 1은 벽(이동할 수 없는 칸)을 나타낸다. 단, 벽을 부수고 이동할 수 있는 기회가 1번 주어지므로 부셨을 때 이동경로가 짧아진다면 부셔도 된다. (1, 1)에서 시작하여 (N,M)까지 가는데 최단거리를 출력하면 된다. 풀이 과정 전형적인 BFS 의 경로찾기 문제에 벽을 부술 수 있다는 특징이 포함된 문제이다. 중간에 .. 더보기
[백준] 1697번 숨바꼭질 (Python 파이썬) www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 설명 수빈이는 동생과 숨바꼭질을 한다. 수빈이의 좌표는 N, 동생의 좌표는 K이다. 수빈이의 위치가 X일 때, 1초 후에 X+1, X-1 X*2 중에 하나로 이동할 수 있다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초인지를 구하면 된다. 풀이 과정 BFS를 이용하여 풀었다. 변수에 대해 먼저 설명하자면, count는 일 수, flag는 찾은 여부를 나타내는 변수이다... 더보기
[백준] 7569번 토마토 (Python 파이썬) www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 설명 가로 M, 세로 N 의 토마토 상자가 H높이만큼 쌓여져 있다. 즉 3차원 배열의 형태로 쌓여져 있다. 이 토마토는 보관 후 하루가 지나면 익은 토마토들의 인접(상하좌우위아래)한 토마토들이 모두 익게 된다. 이 토마토들이 모두 익게되는데 며칠이 걸리는지 최소 일수를 구하면 된다. 풀이 과정 토마토들의 좌표는 graph[x][y][z]로 나타낼 수 있다. 기존 문제들과의 차이점이라.. 더보기
[백준] 1987번 알파벳 (Python 파이썬)(DFS) www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 설명 R x C 크기의 보드판이 있다. 이 보드판의 각 칸에는 대문자 알파벳이 하나씩 적혀있으며, 이 보드판을 움직이는 말은 현재 (1,1)에 위치하고 있다. (시작점에 위치) 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있으며, 새로 이동하는 칸에 적힌 알파벳은 지금까지 지나온 알파벳과 겹쳐서는 안된다. 즉, 같은 알파벳 칸을 두 번 이상 지나갈 수 없다. 좌측 상단부터 시작하여 말이.. 더보기

티스토리툴바