파이썬

[Python/파이썬 백준 5104] 스타트링크(BFS)

www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 일차원 BFS 문제입니다. S,G 를 start, end값으로 선언했으며 U,D 을 dx 값에 +U 와 , -D 를 넣어줬습니다 check 값을 비교해서 queue에 삽입되면 +1씩 시켜줬으며 check[end]를 반환시켜줘서 출력시켰어용~~ # 스타트링크 # 일차원 BFS 문제이며, U,D 을 nx 값에 넣어줘서 # check 해당 값 출력 from collections import deque import sys i..

[Python/파이썬 백준 2206] 벽 부수고 이동하기(BFS)

www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 처음 문제를 봤을 때 이중포문 돌려서 min 값 비교해가면서 풀어봤는데 시간초과가 났습니당! 고래서 검색 결과 check 리스트를 삼중 리스트를 사용해서 z값을 비교해가면서 부술경우 안부술경우를 나누어 풀이 # 이중포문 돌려서 각각 0으로 바꿔서 min값 비교 # 해봤다가 시간초과 돼서 보니까 3차원 쓰라고한당 from collections import deque import sy..

[Python/파이썬 백준 1012] 유기농 배추(BFS)

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 #배추 벌레 문제 bfs 돌때마다 증가 시켜주면 되는데 x,y 신경잘써서 from collections import deque import sys input=sys.stdin.readline T=int(input()) dx=[1,-1,0,0] dy=[0,0,-1,1] for i in range(T): m,n,k=map(int,input().split()) graph=[[0]*m for _ in range(n)] che..

[Python/파이썬, Java/자바 백준 7576] 토마토(BFS)

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 시간초과에 주의해서 표를 입력받을때 1이면 바로 큐에 넣어줬습니다. 이렇게 되면 첫째날 bfs를 할 토마토만 큐 안에 있고, 일자별로 같은 날 들어온 토마토만 bfs 돌리기 위해서 for문에 큐 길이만큼만 돌려주었습니다. 이렇게되면 첫째날 들어온 토마토만큼만 bfs 돌고 result +1 둘째날 들어온 토마토만큼만 bfs 돌고 result+1 . . 이런식으로 탐색하여 result를 리턴시..