글 읽기 - 배추 벌레 다 죽이고 싶지만 참아가며 질문 드립니다..

nkb7714 3년 전 0

배추 벌레 잡기 위해 BFS 로 풀었는데 틀렸습니다가 나오네요.

질문 글에 있는 모든 예시를 다 해보았습니다..

배추 벌레가 있는 위치를 하나 씩 돌며 BFS 를 수행합니다.

이때 방문했었던 위치는 BFS 를 수행하지 않습니다.

즉 BFS 를 수행한 횟수가 그래프의 갯수인데.. 어디가 틀렸는지 아무리 생각해도 모르겠습니다.

BFS 를 시작한 위치를 기준으로 왼쪽, 오른쪽, 위, 아래 위치를 계산 해 배추가 있는 위치이고 방문하지 않았더라면 큐에 넣습니다.

import sys
from collections import deque


def BFS(start_loc):
	queue = deque([start_loc])
	while queue:
		center_loc = queue.popleft()
		cabbage_dict[center_loc] = 'visited'

		x, y = int(center_loc[0]), int(center_loc[1])
		left = str(x - 1) + str(y)
		right = str(x + 1) + str(y)
		up = str(x) + str(y + 1)
		down = str(x) + str(y - 1)

		if left in cabbage_dict and cabbage_dict[left] == 'unvisited':
			queue.append(left)
		if right in cabbage_dict and cabbage_dict[right] == 'unvisited':
			queue.append(right)
		if up in cabbage_dict and cabbage_dict[up] == 'unvisited':
			queue.append(up)
		if down in cabbage_dict and cabbage_dict[down] == 'unvisited':
			queue.append(down)


T = int(input())
output = []

for _ in range(T):
	bugs = 0
	M, N, K = map(int, sys.stdin.readline().rsplit())
	cabbage_dict = dict()
	cabbage_list = list()

	for _ in range(K):
		loc = ''.join(sys.stdin.readline().rsplit())
		cabbage_list.append(loc)
		cabbage_dict[loc] = 'unvisited'

	for start in cabbage_list:
		if cabbage_dict[start] == 'unvisited':
			BFS(start)
			bugs += 1

	output.append(bugs)

for val in output:
	print(val)

sait2000 3년 전 1

12번 줄에서 15번 줄까지가 튜플이 아니라 문자열 덧셈을 하고 있습니다.

nkb7714 3년 전 0

배추가 있는 위치를 문자열로 처리했습니다..

(5, 4) 이 배추가 있는 위치라면 loc = '54' 로 바꾸어 다뤘습니다..

상하좌우를 따질때만 int 로 바꾸어 계산을 해주었구요..

center_loc = '54' 라면 상하좌우는 각각 '55', '53', '44', '64' 가 되도록 했습니다..

혹시 이게 문제가 될까요

sait2000 3년 전 1

네 칸 수가 10칸 이상이면 문제가 됩니다

nkb7714 3년 전 0

(10, 10) 이라면 '1010' 이 되어 1, 0 을 뽑아오는 오류가 있네요..

너무 쉽게 접근하려고 했던 것 같습니다.

제가 넣어봤던 테스트 케이스도 전부 좌표가 한 자리수 이어서 캐치를 못 했나봅니다..

두 시간동안 쩔쩔 맸는데 정말 감사합니다!!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

배추 벌레 다 죽이고 싶지만 참아가며 질문 드립니다..

nkb7714 3년 전 0

sait2000 3년 전 1

nkb7714 3년 전 0

sait2000 3년 전 1

nkb7714 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말