해킹왕 양선규

DFS, 백트래킹 문제이다. 상하좌우 탐색을 요하기 때문에 BFS로도 잠시 생각했었으나 백트래킹이 필요했기에 DFS로 진행했다. 어느정도 정석에 가까운 백트래킹 문제 같다. # DFS, 백트래킹import sysinput = sys.stdin.readline# 입력받기R, C = map(int, input().split())board = []for _ in range(R):    board.append(list(input().strip()))# 사전준비directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]visited = [[False] * C for _ in range(R)]visited[0][0] = Truepath = set() # 집합으로 불필요한 중복 알파벳이 들어..

DFS 문제이다. 진짜 최근에 푼 문제중 가장 어렵고 헷갈렸다.그래프의 싸이클을 찾는 문제이며, 문제만 읽고 싸이클을 찾아야 겠다는 유추를 해내기가 힘들다. 그래프로 옮기는 과정도 힘들고, 싸이클 찾는 로직도 매우 헷갈리고, 단방향인지 양방향인지, 역방향은 결과에 영향을 미치는지, 싸이클을 찾으면 해당 거쳐온 노드를 모두 추가하는 건 안되는지 판단해야 했고.. 하여튼 여러 방향으로 미치는 줄 알았다. # DFSimport sysinput = sys.stdin.readline# 입력받기N = int(input())graph = [[] for _ in range(N + 1)]for i in range(1, N + 1):    graph[i].append(int(input()))def DFS(node, sta..

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번의 반복   ..

DFS 문제이다. 트리가 주어지며, 각 노드는 실외/실내의 특성을 갖는다.산책 루트는 반드시 실내로 시작해서 실내로 끝나야 한다. 그 사이에 실외가 몇개 있든 상관 없다. 이러한 산책 루트가 최대 몇개인지를 출력하면 되는 문제이다. 방향만 바꾼 것도 포함이다. 1->3 , 3->1 이 루트는 별개의 루트이다.  처음엔 문제 지문 그대로 코드로 옮겨 풀었었다.import sysinput = sys.stdin.readlineN = int(input()) # 노드 개수inout = input().strip()inout = [''] + [int(x) for x in inout] # 실내여부, 노드번호와 동기화를 위해 맨앞 빈값 추가graph = [[] for _ in range(N + 1)] # 노드 연결정보,..

import sysinput = sys.stdin.readlineN, M = map(int, input().split())numbers = list(map(int, input().split()))numbers.sort()result = [-1] * Mdef compare(a, b):    if a > b:        return False    return Truedef backTracking(depth):    if depth == M:        print(' '.join(map(str, result)))        return        temp = 0    for i in range(N):        if temp != numbers[i] and (depth == 0 or compare(..

import sysinput = sys.stdin.readlineN, M = map(int, input().split())numbers = list(map(int, input().split()))numbers.sort()result = [-1] * Mdef backTracking(depth):    if depth == M:        print(' '.join(map(str, result)))        return        temp = 0    for i in range(N):        if temp != numbers[i]:            temp = numbers[i]            result[depth] = numbers[i]            backTracking(d..

import sysinput = sys.stdin.readlineN, M = map(int, input().split())numbers = list(map(int, input().split()))numbers.sort()visited = [False] * Nresult = [-1] * Mdef compare(a, b):    if a > b:        return False    return Truedef backTracking(depth):    if depth == M:        print(' '.join(map(str, result)))        return        temp = 0    for i in range(N):        if (depth == 0 and temp != n..

import sysinput = sys.stdin.readlineN, M = map(int, input().split())numList = list(map(int, input().split()))numList.sort()box = []def backTracking(depth):    if depth == M:        print(' '.join(map(str, box)))        return        for i in range(N):        if not numList[i] in box:            box.append(numList[i])            backTracking(depth + 1)            box.pop()backTracking(0) 앞선 N과 M ..

import sysinput = sys.stdin.readline# 1 ~ N 까지의 수 / 길이는 MN, M = map(int, input().split())def backTracking(depth, num):        if depth == M:        print(' '.join(num))        return        for i in range(1, N + 1):        backTracking(depth + 1, num + str(i))backTracking(0, '') 백트래킹이라고 부르기도 좀 민망하긴 하다. 이전 N과 M 문제를 풀면서 올라왔다면 매우 쉽게 풀 것이다. 그냥 1 ~ N 까지의 수, M 길이를 가지는 모든 수열을 출력하면 된다.visited를 사용할 필요도 없..

# 우선 모든 경우의 수 수열을 만드는 코드를 짠다# depth가 0일 땐 바로 재귀 돌린다# depth가 0이 아니라면 "이전 숫자와 비교해 더 클 경우" 재귀 돌린다# num은 str 형태로 전달되며, 비교할 때만 int로 변환해 비교한다# 수열이 완성되면 str형태의 num을 중간에 공백을 추가해서 result 리스트에 담는다# result 리스트의 완성된 수열들을 차례로 출력한다import sysinput = sys.stdin.readline# 1 ~ N 까지의 수 / M개를 고른다N, M = map(int, input().split())visited = [False] * (N + 1) # 수와 인덱스를 맞추기 위해 + 1 한다result = []# 조건 검사 함수def compare(a, b):..