[ 알고리즘 ]/DFS, BFS

[프로그래머스] 프렌즈4블록

📌문제 https://school.programmers.co.kr/learn/courses/30/lessons/17679?language=python3 🎖️난이도 Level 2 ✔️풀이 from collections import deque def check2x2(i, j, m, n, board): if i+1 in range(0, m) and j+1 in range(0, n): if board[i][j] == board[i][j+1] == board[i+1][j] == board[i+1][j+1]: return True return False def replaceTo0(board, visited): for x, y in visited: board[x][y] = 0 def pop_board(m, n, bo..

[프로그래머스] 거리두기 확인하기

📌문제 https://programmers.co.kr/learn/courses/30/lessons/43164 🎖️난이도 Level 2 ✔️풀이 from collections import deque def bfs(graph): dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] for i in range(5): for j in range(5): if graph[i][j] == 'P': queue = deque() queue.append((i, j, 0)) visited = set() visited.add((i, j)) while queue: x, y, d = queue.popleft() for k in range(4): nx = x + dx[k] ny = y + dy[k] nd = d + ..

[백준] 2667. 단지번호붙이기

📌문제 https://www.acmicpc.net/problem/2667 🎖️난이도 ✔️풀이 from collections import deque n = int(input()) graph = [list(map(int, list(input()))) for _ in range(n)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] danji_num = 0 house_num_list = [] for i in range(n): for j in range(n): if graph[i][j] == 1: # bfs queue = deque() queue.append([i, j]) # 첫 시작점의 nx, ny부터 cnt += 1 해주므로, cnt = 1부터 시작 cnt = 1 graph[i][j] =..

[백준] 14502.연구소

📌문제 https://www.acmicpc.net/problem/14502 🎖️난이도 ✔️풀이 from itertools import combinations from collections import deque import copy def getDim(graph, two_xy_list, pos_list, n, m): # 벽 3곳 세우기 G = copy.deepcopy(graph) # 받아온 graph 그대로 쓰면 얕은 복사 돼서 X! (원본에 영향끼침) for i in range(3): x, y = pos_list[i] G[x][y] = 1 # 감염 시작 (bfs) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] for two_pos in two_xy_list: queue = dequ..

[프로그래머스] 불량 사용자

📌문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064 🎖️난이도 Level 3 ✔️풀이 # 2019 카카오 개발자 겨울 인턴십 from itertools import product def isPossible(user_id, banned_id): if len(user_id) != len(banned_id): return False for i in range(len(banned_id)): if banned_id[i] == '*': continue elif banned_id[i] != user_id[i]: return False return True def solution(user_id, banned_id): can_banned = [] fo..