해킹왕 양선규

2022 KAKAO BLIND RECRUITMENT 출제 문제이다.BFS가 메인이고 상태 관리 로직이 필요하다. 카카오 문제들은 자료구조의 선택에 대해서도 많이 생각하게 된다. from collections import defaultdict, dequedef solution(info, edges): """인접 딕셔너리 만들기 (부모 -> 자식 단방향)""" graph = defaultdict(list) for parent, child in edges: graph[parent].append(child) """큐 기본값 설정""" # list는 삭제/탐색연산 느려서 set 쓴다 # 어차피 상태관리 visited로 하고 완전탐색이라 순서 상관없기에 s..

그래프 기초 문제로써, "연결 성분"의 개수를 구하는 문제이다. 즉 연결되지 않은 그래프의 개수를 구하면 된다. 크게 어렵지 않은 문제였다. from collections import dequedef solution(n, computers): table = [[] for _ in range(n)] # 인접리스트 형태 변경 for i in range(n): for j in range(n): if i == j: continue if computers[i][j] == 1: table[i].append(j) visited = [False..

무난한 BFS 문제이다.상하좌우로 연결된 영역이 몇개인지를 출력하면 된다. # 실버2 -> BFS"""T : 테스트 케이스 개수M : 열 ( 가로길이 )N : 행 ( 세로길이 )K : 심어진 배추 개수table : 1은 배추, 2는 방문한 곳"""from collections import dequeimport sysinput = sys.stdin.readlineT = int(input())dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]# 테이블 내에 있고, 배추인지 확인하는 함수def going_no_going(nx, ny, table):    if 0 nx N and 0 ny M and table[nx][ny] == 1:        return True    return Fa..

DFS, BFS 문제이다. 처음에 DFS로 풀어보려 했지만 도저히 머리를 싸매도 감이 안 와서 다른 풀이를 참고해 BFS로 풀었다. 근데 풀고 나니 별로 어렵게 느껴지지가 않는다. 뭐든 그런 것 같다. 해내기 전엔 어렵고 해내고 나면 당연한 게 되고 말이다. # BFSfrom collections import dequeimport sysinput = sys.stdin.readlineN, M = map(int, input().split()) # 행, 열ice = [list(map(int, input().split())) for _ in range(N)]dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1]def iceBreaker():    # 빙산을 녹이고 개수를 세는 작업이 1번의 반복   ..

BFS, 백트래킹 문제이다. 거창한 백트래킹.. 이라기 보다, 그냥 모든 경우의 수를 찾기 위한 부분에서 백트래킹이 사용되었다. BFS가 메인이고 백트래킹은 거드는 느낌의 문제이다. # BFS, 백트래킹# 백트래킹으로 벽 3개를 세우는 경우의 수를 전부 구한 후, BFS로 바이러스를 전파시킨 후 안전 영역의 개수를 센다from collections import dequeimport sysimport copyinput = sys.stdin.readlineN, M = map(int, input().split()) # 행, 열graph = [] # 지도for _ in range(N):    graph.append(list(map(int, input().split())))dx = [-1, 1, 0, 0]dy =..

BFS 문제이다. 불이 1초마다 상하좌우로 1칸씩 퍼지고, 상근이는 1초마다 상하좌우로 1칸씩 이동할 수 있다.건물 끝 4방향의 '.' 빈 공간에 다다르면 탈출에 성공하게 된다. 상근이의 빌딩 탈출에 걸리는 시간을 출력하고, 탈출할 수 없다면 IMPOSSIBLE을 출력하면 된다. import java.io.*;import java.util.*;public class 불_5427 {    static int N; // 테스트 케이스 개수    static int[] dx = {-1, 1, 0, 0};    static int[] dy = {0, 0, -1, 1};    static char[][] tower;    static int[][] visited;    static int w, h;    publ..

L이 육지고 W가 바다이다.상하좌우 육지로만 이동할 수 있다고 했을 때, 보물지도 내에서 가장 먼 두 육지의 거리를 출력하면 된다.물론 두 육지의 거리는 최단거리여야 한다. import java.io.*;import java.util.*;public class 보물섬_2589 {    // 입력값 저장할 변수, 4방향 탐색할 dx dy 선언    static int N, M;    static char[][] maps;    static int[] dx = {-1, 1, 0, 0};    static int[] dy = {0, 0, -1, 1};    public static void main(String[] args) throws IOException {        BufferedReader br =..

# 도치가 사방으로 가는 것과, 물이 도치의 방문목록에 영향을 받는 것(도치가 지나간 길 안가는것)은 결과에 영향을 미치지 않는다. import sys from collections import deque input = sys.stdin.readline R, C = map(int, input().split()) # 행, 열 forest = [list(input().strip()) for _ in range(R)] visited = [[-1] * C for _ in range(R)] # -1로 설정해두고 도치의 이동 과정을 입력할것이다 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] queue = deque() for x in range(R): for y in range(C): if f..

import heapq import sys INF = int(1e9) input = sys.stdin.readline N = int(input()) board = [] for _ in range(N): # 미로 입력받기 board.append(list(map(int, input().strip()))) distroy = [[INF for _ in range(N)] for _ in range(N)] # 부순갯수 visited = [[False for _ in range(N)] for _ in range(N)] # 방문목록 def goingNogoing(x, y): # 갈지말지 정하는함수 if 0

from collections import deque import sys input = sys.stdin.readline M, N, H = map(int, input().split()) # 가로, 세로, 높이 5, 3, 2 box = [] for i in range(N * H): # 토마토 입력받기 box.append(list(map(int, input().split()))) visited = [[False] * M for _ in range(N * H)] # 방문목록 box와 똑같이 만들기 def goingNogoing(box, x, y, visited): # 익힐수있는지 고민하는함수 if 0