www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net from collections import deque m, n = map(int, input().split()) a = [list(map(int, input().split())) for i in range(n)] dx = [-1, 1, 0, 0] # 좌 우 상 하 dy = [0, 0, 1, -1] # 좌 우 상 하 de = deque() def bfs(): while len(de) != 0: x..

www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이 문제는 2667번 단지번호 붙이기 문제와 비슷하다고 생각했다. 2차원배열을 만들어주는 방식만 다르고 탐색하고 덩어리갯수와 덩어리 크기를 구하는 문제였기 때문이다. 좌표를 입력받으면 이차원배열 채우기가 애매하다고 생각이 들 수 있는데 영역을 거꾸로 돌린채로 풀어도 된다. 그래서 풀어봤는데 틀렸습니다가 떴당.. m,n,k = map(int,input().split()) graph = [[0]..

www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진 www.acmicpc.net 처음에 이 문제를 봤을 때 트리구조를 생각했다. 트리구조로 푸려고 하니 도저히 아이디어가 안떠올랐다. 찾아보니 이 문제는 시작지점부터 목표지점까지 몇번 거쳐야하는지 생각하는 단순 탐색 문제였다. bfs로 입력받은 값 기준으로 시작해서 연결되어있는 곳을 찾아 +1씩 더해나가면 문제를 풀 수 있다. 이 문제에서는 인접리스트를 적용하여 풀었다. from collections import deque im..

그래프는 정점과 간선으로 이루어진 자료 구조의 일종이다. 그래프 탐색에 있어 DFS, BFS 방식이 있다. DFS - 깊이 우선 탐색 BFS - 너비 우선 탐색 두 탐색은 모든 정점을 한번만 방문한다는 같은 목표를 가지고 있는데 그 과정에서 탐색하는 방식의 차이가 있다. DFS는 스택을 사용하고, BFS는 큐를 사용한다. 구현에 있어서 인접행렬 또는 인접리스트를 통해 구현할 수 있다. - 정점의 개수가 n개일때 n*n 2차원 배열 - 일반적으로 a라고 이름을 짓는다 - 인접행렬 값이 1이라면 정점간의 간선이 존재하는 것 , 0이라면 존재하지 않는 것 - O(V^2) - 1에 연결되어있는 간선들을 A[1]에 저장, 2에 연결되어있는 간선들을 A[2]에 저장 - O(V+E) [참고자료] [그래프] DFS와 ..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 이 문제는 보아하니 2667번 단지번호붙이기할 때 참고했던 음료수 얼려먹기문제(DFS)와 유사했다. 2667번 문제풀이링크를 참고하겠다.

12813번: 이진수 연산 총 100,000 비트로 이루어진 이진수 A와 B가 주어진다. 이때, A & B, A | B, A ^ B, ~A, ~B를 한 값을 출력하는 프로그램을 작성하시오. www.acmicpc.net 이문제는 비트마스크 문제이다. 기본적인 비트연산자를 이용한 문제인데 not 연산자를 파악하는 데 시간이 걸렸다. 일반적인 not 연산자(~)를 쓰면 결과가 0b0100 -> -0b0101 이런식으로 나와서 not연산자를 사용하지 못했다. 그래서 1의 보수쓰는 법으로 풀었다. ~a를 구하기 위해서 (a가 세자리라면) a^111(mask) 이렇게 xor 연산을 사용해 구하면 된다. ex) a=101 101^111=010 mask값을 구하기 위해서는 이진수가 길이를 알아야하는데 문제에서 1000..