https://www.acmicpc.net/problem/4963흔한 구역 개수 구하는 문제. 근데 특이한 건 대각선도 연결되어 있는 걸로 생각해야 하는 게 특이하다. 그것만 생각하면 나머진 쉬운 문제.아이디어- 일반적인 상하좌우탐색에서 추가로 대각선 방향도 추가해준다.전체 코드import syssys.setrecursionlimit(10**6)dx = [0, 0, 1, -1, 1, -1, 1, -1]dy = [1, -1, 0, 0, 1, -1, -1, 1]def dfs(x, y): if x = H or y = W: return False #print(x, y) if island[x][y] == 1: island[x][y] = 0 dfs(x, y + ..

4179번: 불!입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자www.acmicpc.net 반나절 삽질한 BFS문제. 문제가 어렵게 느껴지진 않았는데 시간초과, 메모리초과 등등 오답파티가 됐다.아이디어- 문제에서 탈출 조건이 가장자리에 접한 공간에서 탈출할 수 있다고 한다. 이 말은 지훈이가 가장자리에 도착만 하면 자동으로 탈출 가능하다. - 순서는 지훈이가 한번 이동하고 나서 불이 확산되고 1초가 지난다. - 만약 지훈이가 이동한 후 위치에 불이 번진다면 그곳은 못 가는 위치이다. - 이 문제를 해결하려면 지훈과 불 각각의 큐를 만들어서..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 활용한 최소 시간을 구하는 문제. 아이디어 현재 위치(x)에서 갈 수 있는 거리는 x - 1, x + 1, x * 2이다. 각 경우마다 if문을 통해 조건을 확인해준다. 이전에 방문하지 않은 위치라면 그 위치까지 걸리는 시간들을 BFS방식으로 순회하며 시간을 저장해준다. 전체 코드 from collections import deque N, K = map(int, input().split()) deq = deque() deq.a..

14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 지도에서 모든 지점의 최단거리를 구하는 문제. 아이디어 BFS를 사용했다. 지도에서 최단거리 == BFS 거의 공식처럼 머리에서 나온다... 문제를 해결하기 위해 목표 지점(2로 표시)과 갈 수 없는 땅(0으로 표시)의 좌표는 따로 저장해 둔다. 전체 코드 from collections import deque dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] start_x, start_y = 0, 0 ..

21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 평범한 그래프 탐색 문제. 아이디어 bfs 또는 dfs를 활용하여 문제를 해결하면 된다. 1. 그래프 시작지역 'I'는 캠퍼스 정보를 받아올 때 미리 찾아둘 수 있다. 2. 빈공간 뿐아니라 사람이 있는 지역 'P'도 이동 가능하다. 3. 정답을 출력할 때, 답이 0명이면 0이 아닌 "TT"를 출력해 주자. 전체 코드 from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] campus =..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 맨해튼 거리인 줄 모르고 삽질했다. 문제를 잘 읽어보자. 아이디어 1. 그래프 탐색 심플하게 맥주 20병 = 1000m라고 생각하고 1000m를 기준으로 갈 수 있는지 없는지 확인하면 된다. bfs를 사용하여 해결했다. 전체 코드 from collections import deque def cal_distance(x, y, nx, ny): return abs(nx - x) + abs(ny -..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 시리즈 마지막 숨바꼭질 1 먼저 풀어보는 게 좋다. 아이디어 1. bfs 큐에 x +1, x - 1, x * 2를 조건에 맞으면 추가해준다. 큐에 위치와 시간 그리고 지나온 길도 같이 넣어준다. 도착하면 도착 시간과 경로를 리턴 후 출력. 전체 코드 from collections import deque N, K = map(int,input().split(..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 1. bfs 이미 숨바꼭질 1과 3을 풀어서 대충 알고 있다. x - 1, x + 1, x * 2 큐에 넣어주면서 탐색하면 됨. 경우의 수를 어떻게 구할지 생각만 하면 된다. 2. 경우의 수 쭉 탐색을 하다가 맨 처음 동생한테 도착한 시간을 저장하고 이후 동생한테 도착했을 때 저장해둔 시간과 같다면 경우의 수를 +1 해준다. 전체 코드 from col..