[Python/파이썬] 백준 2573번: 빙산

문제 풀이 DFS문제, 다만 조금 까다롭게 구현해야 한다. "만일 전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력한다." 해당 조건을 구현하지 않아 62%에서 틀렸습니다가 나왔다. [반례] 5 5 0 0 0 0 0 0 2 2 2 0 0 2 2 2 0 0 2 2 2 0 0 0 0 0 0 답 : 0 틀린 답 : 3 또한 DFS로 풀 경우 sys.setrecursionlimit(10**4) setreucrsionlimit에 너무 큰 값을 넣으면 메모리 초과가 나온다. 주의할 것!! 코드 import sys sys.setrecursionlimit(10**4) input = sys.stdin.readline n, m = map(int, input().split()) graph = [..

[Python/파이썬] 백준 2668번: 숫자고르기

문제 풀이 사이클을 찾는 문제이다. 아래 풀이와 거의 동일하다. https://ku-hug.tistory.com/169 [Python] 백준 9466번: 텀 프로젝트 문제 풀이 사이클을 판별하는 문제이다. 1. 문제에서 주어진 배열을 parent 배열이라 하자. 2. 사이클을 판별하기 위해 이때까지 방문한 노드를 cycle 배열에 저장, 방문 처리를 위해 visited 배열을 생 ku-hug.tistory.com 코드 import sys input = sys.stdin.readline n = int(input()) graph = [0] visited = [False] * (n + 1) cycle = [] ans = [] for _ in range(n): graph.append(int(input())) d..

[Python/파이썬] 백준 9466번: 텀 프로젝트

문제 풀이 사이클을 판별하는 문제이다. 1. 문제에서 주어진 배열을 parent 배열이라 하자. 2. 사이클을 판별하기 위해 이때까지 방문한 노드를 cycle 배열에 저장, 방문 처리를 위해 visited 배열을 생성 3. 1번 노드를 방문했을 때 4. 1번 노드와 연결된 3번 노드 방문 각 노드를 방문하고, 그 노드와 이어진 노드를 계속 방문한다. 만약 이미 방문한 노드이고 사이클 배열에 해당 노드가 존재하면 사이클이 형성되었다는 것이다. 위 과정을 직접 해보면 이해가 쉽다. 코드 import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline def dfs(st): global team visited[st] = True cycle.append(s..

[Python/파이썬] 백준 16929번: Tow Dots

문제 풀이 시작 지점과 같은 문자인 경우 dfs를 수행하고 길이가 4 이상이고 시작 지점으로 돌아온 경우 "Yes"를 출력하면 된다. 코드 import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [list(input().rstrip()) for _ in range(n)] tempVisited = [[False] * m for _ in range(n)] dir = ((0, 1), (0, -1), (1, 0), (-1, 0)) def dfs(c, sti, stj, nowi, nowj, cnt): for dx, dy in dir: ni, nj = nowi + dy, nowj + dx if (sti, stj) == (ni, n..

[Python/파이썬] 백준 1987번: 알파벳

문제 풀이 dfs + 백트래킹으로 풀었다. pypy로 제출 중복된 문자를 체크하기 위해 alpha 배열 생성 (alpha[0] = True인 경우 A칸을 지났다는 의미) alpha = [False] * 26 ord('A') - 65 이런 식으로 인덱스를 맞춰주었다. 그 후 백트래킹을 했다. 코드 import sys input = sys.stdin.readline r, c = map(int, input().split()) graph = [list(input().rstrip()) for _ in range(r)] alpha = [False] * 26 dir = ((0, 1), (0, -1), (1, 0), (-1, 0)) ans = 0 def condition(ni, nj): return ni < 0 or ..

[Python/파이썬] 백준 1068번: 트리

문제 풀이 입력받은 정보를 바탕으로 각 노드의 자식 노드를 저장하는 child 배열을 만들었다. 삭제할 노드의 경우 child 배열에 추가하지 않았다. n = int(input()) parent = list(map(int, input().split())) delNode = int(input()) child = [[] for _ in range(n)] for idx in range(n): if parent[idx] == -1 or idx == delNode: continue child[parent[idx]].append(idx) 자식 노드가 없다는 것은 리프 노드임을 의미 제거할 노드의 자식 노드들을 전부 리프 노드를 만들기 위해 해당 노드에 -1 대입 def dfs(d): # 리프 노드인 경우 if ch..

[Python/파이썬] 백준 1194번: 달이 차오른다, 가자

문제 풀이 비트 마스킹을 사용해 풀었다. 아직 방문하지 않은 상태 : 0b0 키 없음 : 0b1 a키 : 0b10 b키 : 0b100 c키 : 0b1000 a, c키 : 0b1010 ... 이런 식으로 방문 여부를 기록했다. 또한 haveKey에 민식이가 보유한 열쇠 정보를 비트 마스킹했다. 키 없음 : 0b1 a키 보유 : 0b11 b키 보유 : 0b101 a, b키 보유 : 0b111 ... 만약 a, b키를 가진 민식이가 좌표(x, y)에 방문하려 한다. 하지만 해당 좌표에 이미 a, b, c키를 소유한 채로 방문한 적이 있다면 방문할 필요가 없다. if (visited[ni][nj] | haveKey) == visited[ni][nj]: continue 아래 링크를 참고하면 이해하기 쉽다. htt..

[Python/파이썬] 백준 11578번: 팀원 모집

문제 풀이 비트 마스킹을 사용하여 입력 n, m = map(int, input().split()) arr = [0b0000000000] * (m + 1) for i in range(1, m + 1): question = list(map(int, input().split()))[1:] for q in question: arr[i] |= (1

[Python/파이썬] 백준 17472번: 다리 만들기 2

문제 풀이 입력 n, m = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(n)] visited = [[False] * m for _ in range(n)] dir = ((0, 1), (0, -1), (1, 0), (-1, 0)) 섬을 구분 짓기 위해 bfs를 사용한다. def marking(y, x, mark): q = deque() q.append((y, x)) graph[y][x] = mark visited[y][x] = True while q: i, j = q.popleft() for dy, dx in dir: ni, nj = i + dy, j + dx if condition(ni, nj) or n..

[Python/파이썬] 백준 2146번: 다리 만들기

문제 풀이 입력 import sys from collections import deque imput = sys.stdin.readline n = int(input()) graph = [list(map(int, input().split())) for _ in range(n)] visited = [[False] * n for _ in range(n)] dir = ((0, 1), (0, -1), (1, 0), (-1, 0)) 섬을 나누는 과정 0이 아닌 좌표를 발견한 경우 그 좌표와 연결된 값을 전부 mark로 바꾼다. mark = 1 for i in range(n): for j in range(n): if graph[i][j] and not visited[i][j]: marking(i, j, mark) ma..