[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..

[Python/파이썬] 백준 1726번: 로봇

문제 풀이 왼쪽 오른쪽 설정 def turnLeft(now): if now == 1: return 4 #동 북 if now == 2: return 3 #서 남 if now == 3: return 1 #남 동 if now == 4: return 2 #북 서 def turnRight(now): if now == 1: return 3 #동 남 if now == 2: return 4 #서 북 if now == 3: return 2 #남 서 if now == 4: return 1 #북 동 입력 i, j, dir은 로봇의 위치 m, n = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(m)] visited = [[[..

[Python/파이썬] 백준 3055번: 탈출

문제 풀이 입력받는 코드 from collections import deque input = __import__('sys').stdin.readline r, c = map(int, input().split()) graph = [list(input().strip()) for _ in range(r)] waterVisited = [[False] * c for _ in range(r)] dociVisited = [[False] * c for _ in range(r)] water = deque() dx = [0, 0, -1, 1] dy = [1, -1, 0, 0] 굴, 고슴도치, 물의 위치를 찾아주었다. 물 같은 경우 bfs를 수행해야 하므로 deque에 넣었다. # 초기값 설정 for i in range(r)..

[Python/파이썬] 백준 16933번: 벽 부수고 이동하기 3

문제 풀이 n, m, k = map(int, input().split()) graph = [input().rstrip() for _ in range(n)] visited = [[k + 1 for _ in range(m)] for _ in range(n)] visited[0][0] = 0 visited는 도착했을 때 벽을 부순 횟수를 넣는다. 초기 값으로 벽을 최대로 부술 수 있는 횟수를 넣는다. 만약 (x, y) 좌표에서 벽을 부순 횟수(w)가 5번이고, k+1 = 7이라고 가정했을 때 visited[y][x] = 4 인 경우 (x, y) 좌표에 벽을 4번 부수고 방문했다는 뜻 visited[y][x] = 7인 경우 (x, y) 좌표를 아직 방문하지 않았다는 뜻 코드 from collections imp..

[Python/파이썬] 백준 16946번: 벽 부수고 이동하기 4

문제 풀이 1. 0의 묶음을 그룹으로 표시해준다. 2. 각 그룹별로 0의 개수가 몇 개인지 dict를 통해 저장한다. 3. 벽(1)에서 상하좌우로 인접한 그룹을 구한 뒤, 그 그룹에 해당하는 0의 개수를 더해준다. 그룹이 중복되지 않게 set()을 사용한다. 코드 from collections import deque input = __import__('sys').stdin.readline def bfs(start): q = deque() q.append(start) cnt = 1 while q: i, j = q.popleft() zeros[i][j] = group for idx in range(4): ni, nj = i + dy[idx], j + dx[idx] if ni = n or ..

[Python/파이썬] 백준 16954번: 움직이는 미로 탈출

문제 풀이 벽이 한 칸 내려오는 것 = 욱제가 한 칸 위로 올라가는 것 또한 욱제가 맨 위칸으로 올라가기만 하면, 가장 오른쪽으로 갈 수 있다. (1초 뒤에는 욱제와 같은 칸에 있는 벽들이 전부 아래로 내려가고, 욱제는 그 칸에 그대로 있으므로) 코드 from collections import deque input = __import__('sys').stdin.readline n = 8 graph = [list(input().strip()) for _ in range(n)] visited = [[False] * n for _ in range(n)] dx = [0, 0, 1, -1, 1, -1, 1, -1, 0] dy = [1, -1, 0, 0, 1, 1, -1, -1, 0] q = deque() q.ap..

[Python/파이썬] 백준 2448번: 별 찍기 - 11

문제 풀이 위 그림과 통해 규칙을 알 수 있다. N = 6 -> N = 3일 때의 삼각형 3개로 분할 가능 N = 12 -> N = 6일 때의 삼각형 3개로 분할 가능 N = 24 -> N = 6일 때의 삼각형 3개로 분할 가능 ... N= 3인 경우 삼각형을 그린다. 아닐 경우, 이전 상태의 삼각형(N//2) 3개로 분할 (각각에 대해 재귀 호출) 1. 우선 전체 배열을 생성 stars = [[' ']*2*n for _ in range(n)] 2. 분할 정복을 위해 함수 생성 후 n이 3일 때 삼각형을 그려준다. i, j는 좌표 값 def recursion(i, j, size): if size == 3: stars[i][j] = '*' stars[i + 1][j - 1] = stars[i + 1][j ..