•알고리즘(Algorithm )

[백준2583&파이썬] 좌표평면을 배열로 표현하는 방법

# 문제 백준2583 영역구하기 파이썬 풀이 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net # 코드 import sys from collections import deque M,N,K = map(int, sys.stdin.readline().split()) # M 행 , N 열 board = [ [False] * N for i in range(M)] def printBoard() : for i in range(M) : print(board[i]) dirs = [ (-1,0),(0,1),(..

[백준7562&파이썬] BFS를 활용하여 최단거리에 도달하는 방법

# 문제 백준 7562 나이트의 이동 파이썬 풀이 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net # 코드 import sys from collections import deque tc = int(sys.stdin.readline()) dirs = [ (-2,1), (-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1) ] def solve() : l = int(sys.stdin.readline()) # 체스판의 한변의 길이 l * l visit = [ [False] * l fo..

[백준4179&파이썬] 불!/BFS를 이용해 조건에 맞는 최단거리를 구하는 방법

# 문제 백준 4179 불! 파이썬 풀이 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net # 코드 import sys from collections import deque R,C = map(int, sys.stdin.readline().split()) board = list() visit = [ [False for j in range(C) ] for i in range(R) ] j_flag = True f_starting = list() j_pos = [-1,-1] for i in range(..

[백준1926&파이썬] BFS를 활용하여, 연결된 노드의 너비를 세는 방법

# 문제 백준 1926번 그림, 파이썬 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net # 코드 import sys from collections import deque n,m = map(int,sys.stdin.readline().split()) # n 세로크기 , m 가로크기 board = list() visit = [[ False for j in range(m) ] for i in range(n)] for i in range(n) : row = list(map(int,sys.stdin.readline().sp..

[알고리즘] BFS를 이용하여 최단거리를 출력해야할때 with predecesso(프로시져)

# 발단 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS문제는 간선에 가중치가 없는 경우 그래프적으로 해석하면 최단거리를 구할 수 있다. 왜냐하면 노드의 방문을 큐로 관리하기 때문에 넓이우선탐색을 하고 이 넓이는 하나의 turn이 될 수 있다. 그 turn에서 목표지점을 발견했다면 그것이 최단거리이다. 몇몇 BFS문제를 풀었을때, 이러한 최단거리까지 총 몇번의 거쳐서 가는가를 구하는 응용 문제들( ex. 며칠이 걸리나? like 토마토 )은 프로시져를 활용하여 풀었다. 즉 큐에 방문할 당시..

[알고리즘] queue 보다는 deque를 사용하자

# 발단 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net [백준7569] 토마토라는 문제를 풀었다. BFS를 이용하여 탐색과 동시에 가장 빠르게 탐색을 완료하는 시점(단계)를 구하는 문제였다. 3차원이 주어진다는 것 외에는 그렇게 특별한 문제가 아니였기에, 매번 풀던방법과 같이 queue(큐)를 사용하여 문제를 풀었다. DFS는 스택, BFS는 큐를 사용하는 것이 나에게 있어서는 정석과도 같은 방법이었기 때문이다. 그런데 시간초과가 발생했다. 파이썬은 그럴 수 있기에 PyPy로 제출해봤..