분류 전체보기
[백준/5427/파이썬] 불
https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩의 지도가 주어졌을 때..
[백준/6593/파이썬] 상범 빌딩
https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상..
[백준/2468/파이썬] 안전 영역
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 어떤 지역의 높이 정보가 주어진다. 특정 높이 N보다 낮을때, 장마철이 되면 이 지역의 높이정보에 따라 침수여부가 결정된다. 안전지역을 찾아야한다. 이 문제도 , 결국, 연결요소를 찾는 문제이다. 하지만, 연결요소를 찾는 과정에서, 시뮬레이션이 살짝 들어가있는 문제이다. DFS/BFS 둘 다 가능한 문제임. max_height를 먼저 계산해줘서, 침수 될 수 있는 최대 높이를 생각해줬음. ( 사실 높이가..
[백준/10026/파이썬] 적록 색약
https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net BFS/DFS를 조금만 응용하면 되는 문제이다. 항상 DFS/BFS가 가능한지/아닌지 판단하기 위해서 , 시간복잡도를 생각 해줘야 하는데, 이 문제는 연결요소의 갯수를 찾는 문제랑 똑같다. 1. 모든 노드를 방문해야하는가? => 아니다. 한 노드를 시작점으로, 방문해서, 방문한 곳은 방문해줄 필요가 없다.(경우의 수가 달라지지않음. 단, R,G,B가 다 구분되게끔 색칠이 된다면, 모든 노드..
[백준/2583/파이썬] 영역 구하기
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이 문제의 핵심은 DFS/BFS이다. 하지만, 난 그것보단, 좌표 -> 배열로 나타내는 과정이 상당히 인상깊었다. 이 문제는, 사각형의 범위를 시작점 (x1,y1) , 끝나는점(x2,y2)로 나타내었음. 아래와 같이, 빨간영역의 직사각형이라면, 0 1 2 2 로 입력을 한다는 소리임! 컴퓨터의 배열은 0부터 시작하고, 행렬의 개념으로, 좌표의 개념과 다르다. 하지만, 직사각형의..
[백준/2667/파이썬] 단지 번호 붙이기
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net DFS/BFS 문제 중에서, 연결요소 + 연결요소의 크기를 찾는 간단하지만, 중요한 개념이 있는 문제이다. 아래와 같이, 2차원 board를 직접 갖고노는 문제의 기본적인 아이디어 Board 자체를 그래프로 본다. 칸의 배열 => 1개의 노드, 연결여부 -> edge로 생각 입력 예시를 보면, 주황색/초록색/파란색처럼, 아파트 단지가 3개가 생길거임! SOL) 1. v_chk 배열에, True/Fa..
[백준/17289/파이썬] 오큰수
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 조건 크기가 N인 수열 A=a1,a2 - - - An 이 있음. 오큰수 NGE(i)를 구하려고 합니다. An의 오큰수는 An보다 오른쪽에 있으면서, Ai보다 큰 수 중, 가장 왼쪽에 있는 수를 의미합니다. 그러한 수가 없는 경우에, 오큰수는 -1 입니다. 입력 첫째 줄에는 수열 A의 크기 N (1≤N≤10*6)이 주어집니다.둘째 줄에는 수열 A의 원소 A1,A2...An이 주어집니다. SOl) 처음으로 떠오..
[백준/7785/파이썬] 회사에 있는 사람
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 조건 회사의 출퇴근 로그가 주어진다. 로그가 주어졌을때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오. 입력 기록의 수 N이 주어진다. (2≤n≤10^6) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고, enter 나 leave 가 주어진다. enter인 경우는 출근, leave는 퇴근이다. SOL) 이 문제를 ..