chldkato

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net from collections import deque def bfs(x): c = [0 for _ in range(n)] while q: nx = q.popleft() for i in range(n): if c[i] == 0 and a[nx][i] == 1: c[i] = 1 m[x][i] = 1 q.append(i) n = int(input()) a = [list(map(int, input().split())) for _ in range(..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net from collections import deque dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bf..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net from collections import deque def bfs(): while q: x = q.popleft() if x == k: ..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net from collections import deque dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bfs()..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수 www.acmicpc.net dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bfs(x, y, cnt): q = [[x, y]] check[x][y] = cnt wh..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] def bfs(x, y): q = [[x, y]] d[x][y] = 1 while q: x = q[0][0] y = q[0][1] q.pop(0) for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

https://www.acmicpc.net/problem/2931 2931번: 가스관 문제 러시아 가스를 크로아티아로 운반하기 위해 자그레브와 모스코바는 파이프라인을 디자인하고 있다. 두 사람은 실제 디자인을 하기 전에 파이프 매니아 게임을 이용해서 설계를 해보려고 한다. 이 게임에서 유럽은 R행 C열로 나누어져 있다. 각 칸은 비어있거나, 아래 그림과 같은 일곱가지 기본 블록으로 이루어져 있다. 가스는 모스크바에서 자그레브로 흐른다. 가스는 블록을 통해 양방향으로 흐를 수 있다. '+'는 특별한 블록으로, 아래 예시처럼 두 방향 (수직, www.acmicpc.net 1. 각 가스관에서 다음칸으로 이동할 수 있는 방향을 direction 함수에 저장 2. M의 좌표에서 bfs를 실행하고 Z의 좌표에서 b..

https://www.acmicpc.net/problem/2151 2151번: 거울 설치 첫째 줄에 집의 크기 N (1 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다. www.acmicpc.net 방문을 확인할 c 행렬을 3차원으로 해서 3번째 차수를 상하좌우에 대한 방문으로 사용 1. bfs에 입력할 문의 좌표에서 어느 방향으로 이동할 수 있는지 dir 변수에 저장한다 2. bfs로 다음칸에 방문하지 않았거나 현재 c 값보다 크다면 방문하여 갱신한다 3. 방문한..