React Query는 서버 상태(Server State) 를 관리하기 위한 라이브러리다. API 데이터의 캐싱, 동기화, 백그라운드 업데이트를 자동으로 처리해준다.

1. React Query란?

서버 상태 vs 클라이언트 상태

// 클라이언트 상태 (Redux, useState)
const [isModalOpen, setIsModalOpen] = useState(false);
const [theme, setTheme] = useState("dark");

// 서버 상태 (React Query)
const tasks = await fetch("/api/tasks");
const user = await fetch("/api/user");

서버 상태의 특징

• 비동기적으로 불러옴
• 여러 컴포넌트에서 동일 데이터 사용
• 시간이 지나면 stale(낡은 데이터) 상태가 됨
• 캐싱, 동기화, 재요청 로직이 복잡함

-> React Query가 문제를 해결

2. React Query 설치 및 기본 설정

설치

npm install @tanstack/react-query

QueryClient 설정

import { QueryClient, QueryClientProvider } from "@tanstack/react-query";

const queryClient = new QueryClient({
  defaultOptions: {
    queries: {
      staleTime: 5 * 60 * 1000,
      cacheTime: 10 * 60 * 1000,
      refetchOnWindowFocus: false,
      retry: 1,
    },
  },
});

3. 핵심 개념

3.1 Query Key

Query Key는 캐시를 식별하는 고유한 ID다.

queryKey: ["monthlyTasks", accountId, year, month]

요약

적용

기존에 Loader를 사용하여 초기 데이터를 로드하니, 사이드바를 클릭할때마다 api를 호출했었다.

// 초기 데이터 로드 (loader에서 가져온 현재 월 데이터)
  useEffect(() => {
    const loadInitialData = async () => {
      try {
        const tasks = await loaderData.items;
        setCurrentTasks(tasks);
        console.log(tasks);
      } catch (error) {
        console.error("초기 데이터 로드 실패:", error);
      }
    };

    loadInitialData();
  }, [loaderData.items]);

// loaders/index.ts
export const monthlyTasksLoader = () => {
  const accountId = localStorage.getItem("accountId");
  const month = new Date().getMonth() + 1;
  const year = new Date().getFullYear();

  console.error(accountId, month, year);

  const fetcher = createApiCall<MonthlyTasksResponse>(APIS.TASKS.MONTHLY_LIST, {
    accountId,
    month,
    year,
  });

  return createLoaderResultForTask(fetcher);
};

너무 비효율적이어서 React Query를 이용해보았다.

// taskService
export const taskService = {
  // 일일 태스크 조회
  getDailyTasks: async (accountId: string, createdAt: string) => {
    const response = await apiCall<{ totalCount: number; tasks: DailyTasksType[] }>(APIS.TASKS.LIST, { accountId, createdAt });
    return response.tasks;
  },

  // 완료된 태스크 조회
  getCompletedTasks: async (accountId: number) => {
    const response = await apiCall<CompletedTaskListResponse>(APIS.TASKS.COMPLETED_LIST(accountId), {});
    return response;
  },

  // 월별 태스크 조회
  getMonthlyTasks: async (accountId: string, year: number, month: number) => {
    const response = await apiCall<{ totalCount: number; tasks: MonthlyTasksType[] }>(APIS.TASKS.MONTHLY_LIST, { accountId, year, month });
    return response.tasks;
  },
};

API 호출을 서비스로 따로 뺏다.

// (코드 생략) 
  const { data: currentTasks = [], isLoading: loading } = useQuery({
    queryKey: ["monthlyTasks", accountId, currentMonth.year, currentMonth.month],
    queryFn: () => taskService.getMonthlyTasks(accountId, currentMonth.year, currentMonth.month),
    staleTime: 5 * 60 * 1000, 
    cacheTime: 10 * 60 * 1000, 
    refetchOnWindowFocus: false,
    enabled: !!accountId, 
  });


  const handleTodoUpdate = (taskId: number, completed: boolean) => {
    // 캐시 업데이트 (낙관적 업데이트)
    queryClient.setQueryData(["monthlyTasks", accountId, currentMonth.year, currentMonth.month], (old: MonthlyTasksType[] = []) =>
      old.map((task) => (task.taskId === taskId ? { ...task, isCompleted: completed } : task))
    );

    if (selectedTodo && selectedTodo.taskId === taskId) {
      setSelectedTodo((prev) => (prev ? { ...prev, isCompleted: completed } : null));
    }
  };

  const handleTodoDelete = (taskId: number) => {
    // 캐시에서 삭제
    queryClient.setQueryData(["monthlyTasks", accountId, currentMonth.year, currentMonth.month], (old: MonthlyTasksType[] = []) =>
      old.filter((task) => task.taskId !== taskId)
    );

    setIsModalOpen(false);
    setSelectedTodo(null);
  };

그리고 UI에 바로 표시해줘야하는건 캐시 업데이트를 통해 구현을 했다. 일단 월별 보기 화면만 좀 바꿨는데 훨씬 효율적이었다.

  children: [
          { index: true, element: <Navigate to="todo/daily" replace /> },
          {
            path: "todo/daily",
            element: <DailyTodoListPage />,
            loader: dailyTasksLoader, // defer({ totalCount, items }) 반환
          },
          { path: "todo/month", element: <MonthlyTodoListPage /> /* loader: monthlyTasksLoader */ },
          { path: "todo/complete", element: <CompletePage />, loader: completedTasksLoader },
          { path: "groups/own", element: <GroupListPage />, loader: groupListLoader },
          { path: "groups/pending", element: <GroupInvitationPage />, loader: groupPendingListLoader },
          { path: "groups/request", element: <GroupRequestPage />, loader: groupPendingListLoader },
          { path: "groups/joined", element: <JoinedGroupPage />, loader: joinedGroupListLoader },
          { path: "etc/settings", element: <SettingPage /> },
          { path: "*", element: <ErrorPage /> },
        ],

라우터도 일단 주석처리를 했다.

더이상 사이드바를 아무리 클릭해도 api호출이 되지 않았다.

React Query는 언제 쓰는 게 좋을까?

무조건 쓰는 라이브러리는 아니다.
“서버 상태”일 때만 쓰는 게 정답이다.

한 줄 결론

서버에 저장된 데이터 -> React Query
UI·임시·입력 상태 -> React Query 사용 x

React Query 사용하기 좋은 곳

1. 서버에서 가져오는 데이터 (조회)

- 사용자 목록
- 할 일(Task) 리스트
- 게시글 / 댓글
- 월별 캘린더 데이터

특징

• API 호출 결과
• 여러 컴포넌트에서 공유
• 캐싱 가치가 있음

👉 useQuery 사용

2. 목록 + 상세 구조

useQuery(["posts"], fetchPosts);
useQuery(["post", postId], fetchPost);

장점

• 뒤로 가기 시 API 재호출 x
• 캐시 재사용으로 UX 향상

3. 페이지 전환이 잦은 데이터

queryKey: ["tasks", userId, year, month];

• 캘린더
• 탭 이동
• 필터 변경

4. 서버와 동기화되는 상태 (CRUD)

useMutation(updateTask, {
  onMutate: optimisticUpdate,
});

• 낙관적 업데이트
• rollback 가능

5. 여러 컴포넌트에서 공유되는 서버 데이터

useQuery(["user"]);

Redux 없이도 충분한 경우 많음

React Query 사용하면 안 좋은 곳

1. 순수 UI 상태

const [isModalOpen, setIsModalOpen] = useState(false);
const [selectedTab, setSelectedTab] = useState("calendar");

2. 폼 입력값

const [title, setTitle] = useState("");

3. 단발성 요청

useEffect(() => {
  fetch("/health-check");
}, []);

4. 계산된 값 / 파생 상태

const completedCount = tasks.filter(t => t.done).length;

판단 기준

정리

서버에서 오고, 저장되고, 공유되는 데이터 → React Query
UI·입력·임시 상태 → useState / useReducer

구글링을 해본 결과 한 벨로그에서 정리를 잘 해주셨다.

https://velog.io/@jonghyun3668/SpringBoot-%EB%A9%80%ED%8B%B0-%EB%AA%A8%EB%93%88-%ED%94%84%EB%A1%9C%EC%A0%9D%ED%8A%B8%EC%97%90%EC%84%9C-%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%99%98%EA%B2%BD-%EC%84%A4%EC%A0%95%ED%95%98%EA%B8%B0

멀티모듈 프로젝트는 SpringBootApplication을 모듈에 넣어놓고 테스트를 진행하는데 이게 없어서 에러가 났던 것이다.

이렇게 @SpringBootApplication을 모듈 안에 넣어준 후 테스트를 하니 정상적으로 작동하였다.

반대로 단위 테스트를 진행할 때는 Mock를 사용하여 실행을 했는데, 여기서 Mock랑 SpringBootTest의 차이점을 찾았다.

@SpringBootTest와 같은 테스트에서는 실제로 스프링 애플리케이션 컨텍스트를 로드한다. 이 경우 테스트할 때 해당 애플리케이션 컨텍스트의 설정이 필요하기 때문에 @SpringBootApplication이 있는 클래스를 지정해주어야 한다.

하지만, Mockito와 같은 단위 테스트를 수행할 때는 전체 애플리케이션 컨텍스트를 로드할 필요가 없다. 이 경우 테스트하고자 하는 특정 클래스에 대한 단위 테스트를 수행하며, 해당 클래스의 의존성을 Mocking하는 것이 목적이다. 따라서, 단위 테스트에서는 @SpringBootApplication 클래스를 지정할 필요가 없다.

차이점 요약

@SpringBootTest 사용 시

[1] 컨텍스트 로딩: 스프링 애플리케이션 컨텍스트를 로드하고 모든 빈을 초기화한다. [2] 테스트 대상: 통합 테스트 또는 여러 빈 사이의 상호작용을 테스트할 때 사용한다. [3] 필요사항: @SpringBootApplication이 있는 클래스를 지정해야 하며, 멀티 모듈 프로젝트에서는 해당 모듈의 애플리케이션 클래스를 지정해줘야 할 수 있다.

Mockito 단위 테스트 사용 시

[1] 컨텍스트 로딩: 스프링 컨텍스트를 로드하지 않으며, 특정 클래스의 의존성을 Mocking하여 단위 테스트를 수행한다. [2] 테스트 대상: 개별 클래스나 메서드의 동작을 검증하는 데 초점이 맞춰져 있다. [3] @SpringBootApplication 클래스를 지정할 필요가 없으며, 단순히 필요한 의존성만 Mocking하면 된다.

class ComnErrorCodeListInitTest {

    @Mock
    private ComnErrorCodeDaoMapper comnErrorCodeDaoMapper;

    @InjectMocks
    private ComnErrorCodeListInit comnErrorCodeListInit;

    @BeforeEach
    void setUp() {
        MockitoAnnotations.openMocks(this);
    }

    @Test
    void testInitEntities() {
        // Given
        ErrorCodeEntity duplicateGroupErrCode = new ErrorCodeEntity();
        duplicateGroupErrCode.setErrorCode("EC_G_001");

        ErrorCodeEntity notFoundGroupErrCode = new ErrorCodeEntity();
        notFoundGroupErrCode.setErrorCode("EC_G_002");



        ErrorCodeEntity duplicateIdErrCode = new ErrorCodeEntity();
        duplicateIdErrCode.setErrorCode("EC_A_001");


        List<ErrorCodeEntity> errorCodeEntities = Arrays.asList(
                duplicateGroupErrCode,
                notFoundGroupErrCode,
                duplicateIdErrCode
        );

        // When
        when(comnErrorCodeDaoMapper.getErrorCodes(new ErrorCodeEntity())).thenReturn(errorCodeEntities);
        comnErrorCodeListInit.initOptionData();

        // Then
        List<ErrorCodeEntity> result = comnErrorCodeListInit.getErrorCodeEntities();
        assertEquals(4, result.size());
        assertEquals("EC_G_001", result.get(0).getErrorCode());
        assertEquals("EC_G_002", result.get(1).getErrorCode());
        assertEquals("EC_A_001", result.get(2).getErrorCode());
    }
}

에러코드 몇개만 가지고 와봤다. 결과는 성공 !

다음에는 공통코드에서 에러코드가 DB에 추가되었을때, 동기화하는 기능을 구현할 예정이다.

지금 회사에서 진행중인 프로젝트도 내가 서버개발에 다른 책임님께서 안드로이드 개발을 진행중인데, 안드로이드 9부터는 http를 아예 막아놓았다는 얘기가 어렴풋이 기억이 났었다.

스택오버플로우에도 해당 자료가 많았는데

https://stackoverflow.com/questions/51902629/how-to-allow-all-network-connection-types-http-and-https-in-android-9-pie

해당 방법이 제일 잘 알려져 있어서 그대로 했는데 자꾸 cleartext에러가 났다....

알고보니 Retrofit 설정에서

import okhttp3.ConnectionSpec
import okhttp3.OkHttpClient
import okhttp3.logging.HttpLoggingInterceptor
import retrofit2.Retrofit
import retrofit2.converter.gson.GsonConverterFactory
import java.util.Arrays
import java.util.concurrent.TimeUnit


object WebServiceClient {
    private lateinit var interceptor: HttpLoggingInterceptor
    private lateinit var okHttpClient: OkHttpClient
    private var retrofit: Retrofit? = null


    val client: Retrofit
        get() {
            interceptor = HttpLoggingInterceptor()
            interceptor.level = HttpLoggingInterceptor.Level.BODY
            okHttpClient = OkHttpClient.Builder()
                .addInterceptor(interceptor)
                .connectionSpecs(
                    Arrays.asList(
                    ConnectionSpec.MODERN_TLS,
                    ConnectionSpec.COMPATIBLE_TLS,

                    //// 이줄을 추가해줘야 했었음.
                    ConnectionSpec.CLEARTEXT))
                .followRedirects(true)
                .followSslRedirects(true)
                .retryOnConnectionFailure(true)
                .connectTimeout(20, TimeUnit.SECONDS)
                .readTimeout(20, TimeUnit.SECONDS)
                .writeTimeout(20, TimeUnit.SECONDS)
                .cache(null)
                .build()

            if (retrofit == null) {
                retrofit = Retrofit.Builder()
                    .baseUrl("개발서버URL")
                    .addConverterFactory(GsonConverterFactory.create())
                    .client(okHttpClient)
                    .build()
            }
            return retrofit!!
        }
}

ConnectionSpec.CLEARTEXT 이걸 추가해줘야 했었다.

❓ 문제

백준 실버2 문제 > 이동하기

❗ 해결

이동은 오른쪽 아래, 위 또는 대각선으로만 이동이 가능하다. 값을 누적해줄 dp 테이블을 하나 생성해준다.

1 2 3 4 0 0 0 5 9 8 7 6

이렇게 있을 때

반복문을 두번 돌린다.

for i in range(n):
    for j in range(m):

i(행)가 0이거나 n, 즉 행의 맨 끝이나 맨 처음일 때는 j-1에 있는 값에 누적해주고 j(열)이 0이거나 m 일대는 i-1에 있는값만 누적하고, 그 외의 경우

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 현재 값

을 누적해주면 된다.

n,m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] * m for _ in range(n)]

dp[0][0] = maze[0][0]

for i in range(n):
    for j in range(m):

        if i == 0 or i == n:
            dp[i][j] = dp[i][j-1] + maze[i][j]
        elif j == 0 or j == m:
            dp[i][j] = dp[i-1][j] + maze[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + maze[i][j]

print(dp[n-1][m-1])

조금 더 쉽게 풀수 있는 방법이 있었다..

다른분의 코드 https://dailylifeofdeveloper.tistory.com/122

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
dp = [[0] * (M + 1)] * (N + 1)
candy = []

for i in range(N):
    candy.append(list(map(int, input().split())))

for i in range(1, N+1):
    for j in range(1, M+1):
        dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + candy[i-1][j-1]

print(dp[N][M])

기저상태 설정하는게 좀 달라서 그랬던것 같은데.. dp는 아직 많이 풀어봐야할것 같다. 뭔가 점화식은 도출하는데 성공했지만, 아직 많이 부족하다..

풀긴 했는데 뭔가 찜찜한 이 느낌

❓ 문제

백준 실버1 문제 > 정수 삼각형

❗ 해결

DP 문제인데 조금 생각하다 보니 풀이법이 떠올랐다.

양 끝에 있는 숫자들은 어차피 더해지는게 정해진다.

즉, 리스트를

arr = [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]

이렇게 만들고,

반복문을 두번 돌린다.

for i in range(1,n):
    for j in range(len(arr[i]):

그러면 1번째 7, 2번째 3,8 3번째 8,1,0 ... 이 될것이다.

양 끝에 있는 숫자들은 바로 위에 숫자를 더해준다. 즉 j의 index가 0이거나 arr의 길이 - 1일때 바로위의 숫자를 더해주면 된다.

if j == 0:
    d[i][j] = d[i-1][j] + arr[i][j]
elif j == len(arr[i])-1:
    d[i][j] = d[i-1][j-1] + arr[i][j]

그렇지 않은 경우 문제에서 오른쪽이나 왼쪽 대각선의 수만 더할 수 있다고 했으므로

오른쪽이나 왼쪽 대각선의 수 중 더 큰수를 넣으면 된다.

else:
    d[i][j] = max(d[i-1][j-1], d[i-1][j]) + arr[i][j]

중간에 반례를 못찾아서 조금 헤맷는데,

처음 반복문을 1부터 시작해야지, 0으로 시작했다가 입력이

1 1

이면 2가 되는 상황이 발생해서.. 수정했다.

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

d = [[0 for _ in range(n)] for _ in range(n)]

d[0][0] = arr[0][0]

for i in range(1, n):
    for j in range(len(arr[i])):
        if j == 0:
            d[i][j] = d[i-1][j] + arr[i][j]
        elif j == len(arr[i])-1:
            d[i][j] = d[i-1][j-1] + arr[i][j]
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + arr[i][j]

print(max(d[n-1]))

젠킨스를 사용해서 현재 사용중인 local gitea에 푸시 이벤트 발생 시 자동으로 빌드되도록 설정 했다.

이쪽이 설명이 굉장히 잘되있으므로 참고해서 하면 된다. 참고 : https://velog.io/@thdrldud369/CICD-%EA%B5%AC%EC%B6%95-2.-Jenkins-%EC%99%80-Gitea-%EC%97%B0%EB%8F%99

그런데 Scan Multibranch Pipeline Log를 실행해도 Jenkinsfile을 찾았는데 자동 빌드가 되지 않았다.

이상해서 Gitea의 Webhook 기록을 찾아봤는데

deny... ?

뭔가 거부됐다고 로그 메시지가 나와있었다.

바로 구글링을 해본 결과

https://forum.gitea.com/t/jenkins-pipeline-creation-with-gitea-for-webhook-trigger/7830/2

나랑 똑같은 현상을 겪을 사람이 있었다.

공식 문서 링크를 보니 ALLOWED 된 HOST 만 가능하도록 Gitea에서 설정해줘야 했다.

C:\Gitea\custom\conf 의 app.ini에서 Allowed host list를 설정해주고 ip를 허용해줘야 했다.

app.ini에

[webhook] ALLOWED_HOST_LIST = 192.xxx.xxx.xxx 를 입력해준다.

저장하고 Gitea를 재시작 해준다. 나는 windows service에 등록했기 때문에 서비스를 재시작 하면 된다.

Jenkinsfile을 수정하고 푸시 했다.

제대로 올라오는 것을 볼 수 있다.. 근데 실패....

또 에러가 발생했다..

https://stackoverflow.com/questions/45140614/jenkins-pipeline-sh-fail-with-cannot-run-program-nohup-on-windows 찾아보니 git bash 관련 문제였다.(역시 스택오버플로우)

해당 해결법을 적용하고 다시 빌드 했다.

잘 된다 !!

❓ 문제

프로그래머스 Lv.2 문제 > 혼자 놀기의 달인

❗ 해결

https://www.acmicpc.net/problem/2346 백준 풍선 터뜨리기랑 비슷한 느낌의 문제였다. 다행히 카드 길이가 100장 이하길래 아 완전탐색으로 풀어도 되겠구나..싶었음.. 설명은 주석으로 달았다.

def solution(cards):

    # 이미 열어본 상자인지 확인
    opened = [False] * len(cards)
    group = []

    # 카드 배열을 순회하면서 
    for index, value in enumerate(cards):

        # 카운트 변수를 0으로 초기화 해준다.
        cnt = 0
        while True:
            # 만약에 순회하다가 이미 연 상자를 만났으면(순회가 끝났으면)
            # 카드 그룹에 카드 개수를 append해주고 반복문을 빠져 나온다.
            if opened[index]:
                group.append(cnt)
                break

            # 열지 않은 상자라면 
            # 열었다는 표시 (opened[index]를 True로 바꿔준다.)
            # 그리고 index를 상자안에 담긴 카드 숫자로 변경한다.
            # 카드값을 갱신해주고, 카드 카운트 수를 1 증가시킨다.
            if not opened[index]:
                opened[index] = True
                index = value - 1
                value = cards[index]
                cnt += 1
    # 그룹을 정렬 해준다.
    group.sort(reverse=True)

    # 만약 group의 길이가 1개라면 ( 그룹이 한개밖에 존재하지 않는다면 점수는 0)
    if len(group) == 1:
        return 0
    # 그렇지 않다면 첫번째 그룹과 두번째 그룹을 곱한 값을 반환해준다.
    else:
        return group[0] * group[1]

❓ 문제

백준 골드5 문제 > 적록색약

❗ 해결

BFS로 풀었다.

먼저 적록색약이 아닌 사람부터 구하고, 그다음 적록색약인 사람을 구했다.

n = int(input())
board = []

visited = [[0] * n for _ in range(n)]

dic = {'R': 1, 'G': 2, 'B': 3}

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

normal_count = 0
red_green_blind_count = 0

for _ in range(n):
    s = str(input())
    temp_list = []
    for char in s:
        temp_list.append(dic[char])

    board.append(temp_list)

나는 보기 편하게 그냥 숫자로 바꿔줬는데, 그냥 문자열을 숫자로 안바꾸고 풀어도 된다. 내가 한게 비효율적인듯.. 그래도 숫자가 보기 편해서 숫자로 바꿔서 풀었다.

# 적록색약이 아닌 사람
for color in range(1, 4):
    # 1번부터 시작 한다.
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                normal_count += 1

그리고 적록색약이 아닌 사람부터 시작한다. 적록색약이 아닌 사람은 RGB를 다 볼수 있으니, 바깥쪽 반복문에서 1,2,3 순서대로 구한다.

def bfs(x, y, color):

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append([x, y])
    visited[x][y] = 1

    while queue:

        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and board[nx][ny] == color:
                visited[nx][ny] = 1
                queue.append([nx, ny])

bfs 함수이다. 현재 색상을 파라미터로 넘겨줘서 해당 색상만 찾도록 조건을 걸었다.

# 적록색약인 사람
# 방문한 곳을 체크하는 리스트를 초기화해줌.
visited = [[0] * n for _ in range(n)]

# G(2)면 R(1)로 전부 통일 한다.
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            board[i][j] = 1

for color in [1, 3]:
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                red_green_blind_count += 1

print(normal_count, red_green_blind_count)

다 찾았으면 적록색약인 사람이 봤을 때 나오는 구역의 수를 구한다. 이때 방문한 곳을 체크하는 리스트는 다시 0으로 초기화를 해주고, 적록색약인 사람은 R,G를 구분하지 못하므로 G를 R로 바꿔주었다 ( 2-> 1 )

그리고 똑같이 bfs 함수를 실행한다.

전체코드

from collections import deque

def bfs(x, y, color):

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append([x, y])
    visited[x][y] = 1

    while queue:

        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and board[nx][ny] == color:
                visited[nx][ny] = 1
                queue.append([nx, ny])


n = int(input())
board = []

visited = [[0] * n for _ in range(n)]

dic = {'R': 1, 'G': 2, 'B': 3}


normal_count = 0
red_green_blind_count = 0

for _ in range(n):
    s = str(input())
    temp_list = []
    for char in s:
        temp_list.append(dic[char])

    board.append(temp_list)

# 적록색약이 아닌 사람
for color in range(1, 4):
    # 1번부터 시작 한다.
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                normal_count += 1

# 적록색약인 사람
# 방문한 곳을 체크하는 리스트를 초기화해줌.
visited = [[0] * n for _ in range(n)]

# G(2)면 R(1)로 전부 통일 한다.
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            board[i][j] = 1

for color in [1, 3]:
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                red_green_blind_count += 1

print(normal_count, red_green_blind_count)

❓ 문제

백준 실버1 문제 > 영역 구하기

❗ 해결

BFS로 풀었다.

예제 입력에서 5 7 3 이 들어오고 5행 7열짜리 모눈종이와 좌표 3개가 주어진다. 좌표는 (x1, y1) (x2, y2) 형태로 주어진다. 예제에서 (0,2) 부터 (4,4)까지 칠하고, (1,1)부터 (2,5)까지 칠하고 (4,0)부터 (6,2)까지 칠한다. 이것을 코드로 옮겨 보면

m, n, k = map(int, input().split())
board = [[0] * n for _ in range(m)]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(x1, x2):
        for j in range(y1, y2):
            board[j][i] = 1

먼저 5행 7열짜리 모눈종이는 전부 0으로 초기화하고 좌표를 입력 받아서,해당 좌표 범위 내에 있는 영역은 전부 1로 채워 넣는다 (=칠한다)

count_list = []
area_count = 0

for i in range(len(board)):
    for j in range(len(board[0])):
        if board[i][j] == 0:
            count_list.append(bfs(i, j))
            area_count += 1

그리고 각 영역의 넓이를 담아줄 count_list 와 해당 영역 개수를 담아줄 area_count를 선언한다.

그리고 모눈종이를 반복문으로 돌리면서 칠해지지 않은 곳(=0인 곳)이 있을 경우 bfs를 한다.

def bfs(x, y):
    count = 1
    queue = deque()
    board[x][y] = 1
    queue.append([x, y])

    while queue:

        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] != 1:
                board[nx][ny] = 1
                queue.append([nx, ny])
                count += 1

    return count

처음 count는 1로 초기화 해준다(칠하지 않은 곳을 만났으므로) 그리고 해당 방문한 곳은 1로 변경해주고, 1이 아닌 곳을 돌면서 count를 누적시켜준다. 그리고 마지막에 count를 반환한다.

전체코드

from collections import deque

def bfs(x, y):
    count = 1
    queue = deque()
    board[x][y] = 1
    queue.append([x, y])

    while queue:

        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] != 1:
                board[nx][ny] = 1
                queue.append([nx, ny])
                count += 1

    return count


m, n, k = map(int, input().split())
board = [[0] * n for _ in range(m)]

count_list = []
area_count = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(k):
    x1, y1, x2, y2 = map(int, input().split())

    for i in range(x1, x2):
        for j in range(y1, y2):
            board[j][i] = 1

for i in range(len(board)):
    for j in range(len(board[0])):
        if board[i][j] == 0:
            count_list.append(bfs(i, j))
            area_count += 1

print(area_count)
print(*sorted(count_list))

❓ 문제

백준 실버1 문제 > 스타트링크

❗ 해결

조금만 읽어보니 BFS 문제다.

1부터 10까지 있고, 내가 10이라는 포인트를 가고 싶다. 현재 위치는 1이고 나는 한번에 앞으로 2칸 가거나 뒤로 1칸 밖에 못간다. 해당 포인트까지 가는 최소 횟수를 구해라

이렇게 문제를 바꿔 보았다. 그러면, 2차원 BFS가 아니고 1차원 BFS가 된다.

처음에 입력값을 받고 방문했던 곳을 체크할 visited 리스트와, 방문 횟수를 누적해줄 check라는 리스트를 선언해준다.

from collections import deque

f,s,g,u,d = map(int, input().split())
visited = [0] * (f+1)
check = [0] * (f+1)

그리고 시작할 층이 정해져 있다.

queue = deque([s])
directions = [u, -d]
visited[s] = 1
check[s] = 1

시작할 층을 큐에 처음 넣어 준다. 방향은 위, 아래 두개밖에 없다.

while queue:

    current = queue.popleft()

    for i in range(2):

        move = current + directions[i]

        if 0 < move <= f and visited[move] == 0:
            visited[move] = 1
            check[move] = check[current] + 1
            queue.append(move)

큐를 반복하면서 건물 범위에 벗어나지 않고 방문하지 않은 곳이면 해당 위치를 방문해준다.

from collections import deque

f,s,g,u,d = map(int, input().split())

visited = [0] * (f+1)
check = [0] * (f+1)

queue = deque([s])
visited[s] = 1
check[s] = 1

directions = [u, -d]

while queue:

    current = queue.popleft()

    for i in range(2):

        move = current + directions[i]

        if 0 < move <= f and visited[move] == 0:
            visited[move] = 1
            check[move] = check[current] + 1
            queue.append(move)


if check[g] == 0:
    print('use the stairs')
else:
    print(check[g] - 1)

마지막에 현재 층에서 check를 1로 해줬으니 빼주고 출력한다. 만약 check[g]가 0이면 엘리베이터로 갈 수 없는 곳이라고 간주 한다.

❓ 문제

백준 브론즈4 문제 > 알파벳 개수

❗ 해결

아스키코드로 풀면 될것 같았다. 문제에서 a부터 z까지 소문자 알파벳으로만 이루어져 있다고 했다.

alphabet = [i for i in range(97,123)]
answer = [0] * (123-97)

이렇게 a(97)부터 z(122)까지 리스트를 선언 한다. 그리고 입력받은 문자열을 반복하면서 해당 문자마다 아스키코드로 변환해서, alphabet라는 리스트의 index를 구해서 값을 1씩 올려주면 간단하게 해결이 된다.

전체코드

alphabet = [i for i in range(97,123)]
answer = [0] * (123-97)
string = str(input())

for char in string:
    answer[alphabet.index(ord(char))] += 1

print(*answer)

❓ 문제

백준 브론즈2 문제 > 방 배정

❗ 해결

범위에 제한이 있다. 남/여 1학년~6학년 까지이므로 한정된 크기의 리스트를 사용해서 학생들의 방을 배정했다.

이렇게 성별/학년을 가르키는 2행 6열짜리 배열을 선언한 후, 입력이 들어올 때 마다 방 안에 넣어버리면 된다.

n, limit = map(int, input().split())
rooms = [[0] * 7 for _ in range(2)]
for _ in range(n):
    gender, grade = map(int,input().split())
    rooms[gender][grade] += 1

이렇게 되면 예제 입력 1을 넣게 되면 테이블이 이렇게 찬다. 그대로 방의 개수(값이 0이 아닌것을 카운트)를 세어주면 되는데 여기서 주의할 점은 문제에서 방의 정원이 n명인데, 방 안에 n+1명이 들어가면 새로운 방이 필요하다고 했다.

즉 빨간색 네모 부분에 3학년 남학생이 세명이나 있어 새로운 방이 필요할 것이다. 처음에는 단순히 정원을 초과했을 경우에

방 개수 += (해당 방에 있는 총 인원 // 정원) + 1 이렇게 코드를 작성했는데, 이렇게 되면 방에 4명이 있고 정원이 2명이면 (4 // 2) + 1 이 되어서 실제로는 방이 두개만 있으면 되는데 세개로 늘어나버려 자꾸 실패하는 실수를 했다. 그래서 방에 있는 사람과 방의 정원을 나눴을 때 나누어 떨어지면 그냥 몫만 구해서 방 개수에 누적해주고 나누어 떨어지지 않으면 +1 해주는 로직을 짰다.

for i in range(len(rooms)):
    for j in range(len(rooms[0])):

        # 위의 테이블을 돌면서
        # 방에 적어도 한명이상 존재하는 값만 카운트 한다.
        if rooms[i][j] != 0:
            # 근데 방 정원보다 많은 방의 경우
            if rooms[i][j] > limit:
                # 나누어 떨어지면 
                if rooms[i][j] % limit == 0:
                    count += rooms[i][j] // limit
                # 나누어 떨어지지 않으면
                else:
                    count += (rooms[i][j] // limit) + 1
            else:
                count += 1

print(count)

전체코드

n, limit = map(int, input().split())
rooms = [[0] * 7 for _ in range(2)]
count = 0

for _ in range(n):
    gender, grade = map(int,input().split())
    rooms[gender][grade] += 1

for i in range(len(rooms)):
    for j in range(len(rooms[0])):
        if rooms[i][j] != 0:
            if rooms[i][j] > limit:
                if rooms[i][j] % limit == 0:
                    count += rooms[i][j] // limit
                else:
                    count += (rooms[i][j] // limit) + 1
            else:
                count += 1

print(count)

한참 헤맬 때 눈물겨운 2점 기록들 .........

P.S

4 2
1 1
1 1
1 1
1 1

정답 : 2
내 출력 : 3

이 반례가 로직 수정에 도움이 제일 많이 되었다.

❓ 문제

백준 실버 3 문제 > 프린터 큐

❗ 해결

큐를 사용해서 풀면 된다. 먼저 문서의 index와 해당 문서의 중요도를 리스트 형태로 저장한다.

입력이 6 0 1 1 9 1 1 1

일때,

[[0 , 1], [1, 1], [2, 9], [3, 1], [4, 1], [5, 1]]

이렇게 만들어주도록 한다.

count, target = map(int,input().split())

temp = list(map(int,input().split()))

documents = deque()
for i, v in enumerate(temp):
    documents.append([i,v])

그러면 documents라는 리스트는 위의 리스트와 같은 형태를 나타낸다.

 rank = 0
    while documents:

        flag = False
        temp = documents.popleft()

        for doc in documents:

            if temp[1] < doc[1]:
                flag = True
                break

        if flag:
            documents.append(temp)
        else:
            rank += 1

            if temp[0] == target:
                print(rank)
                break

그 후 몇 번째로 출력되는지를 나타내는 rank 변수를 0으로 초기화 시켜준다.

그리고 documents가 빌 때 까지 (모든 문서가 인쇄될 때 까지) while문을 돌리면서 문서 맨 앞부터 popleft()를 해서, 리스트를 순회하면서 중요도가 높은 문서가 있는 경우 flag 값을 True로 변경해주고, 마지막에 flag값이 True인 경우에는 중요도가 있는 문서가 존재하기 때문에 해당 popleft() 한 문서를 맨 뒤로 보낸다.

만약 flag가 False인 경우 해당 문서가 가장 중요한 문서이므로 출력한다. 출력할 때 출력한 순서를 나타내는 rank값을 1씩증가시키면서, 찾는 문서가 나온 경우 rank값을 출력시켜주고 반복문을 빠져나온다.

전체코드

from collections import deque

case = int(input())

for _ in range(case):

    count, target = map(int,input().split())

    temp = list(map(int,input().split()))

    documents = deque()
    for i, v in enumerate(temp):
        documents.append([i,v])

    rank = 0
    while documents:

        flag = False
        temp = documents.popleft()

        for doc in documents:

            if temp[1] < doc[1]:
                flag = True
                break

        if flag:
            documents.append(temp)
        else:
            rank += 1

            if temp[0] == target:
                print(rank)
                break

Hospital.java

.
.
.

 @OneToMany(mappedBy = "hospitals", cascade = CascadeType.REMOVE, fetch = FetchType.LAZY)
    @OrderBy("id asc")
    private List<Member> members;

Member.java

 .
 .
 .
  @JsonIgnore
    @ManyToOne
    @JoinColumn(name = "hospitals_id")
    private Hospital hospitals;

 @OneToMany(mappedBy = "members", cascade = CascadeType.REMOVE, fetch = FetchType.LAZY)
    private List<Equipment> equipments;

Equipment.java

@JsonIgnore
@ManyToOne
@JoinColumn(name = "members_id")
private Member members;

Hospital 안에 Member, Member안에 Equipments 이런 구조를 가지고 있다. 여기 있는 모든 데이터를 조회 하려고 Repository에서 JPQL을 작성하였다.

@Query("SELECT DISTINCT h " +
            "FROM Hospital h " +
            "LEFT JOIN FETCH h.members m " +
            "LEFT JOIN FETCH m.equipments e " +
            "ORDER BY h.hospitalName")
List<Team> findAllWithMembersAndEquipments();

실행 하니

org.hibernate.loader.MultipleBagFetchException: cannot simultaneously fetch multiple bags: 

이런 에러가 발생하였다.

그래서 Fetch Join을 제거하고

@Query("SELECT DISTINCT h " +
            "FROM Hospital h " +
            "LEFT JOIN h.members m " +
            "LEFT JOIN m.equipments e " +
            "ORDER BY h.hospitalName")
List<Team> findAllWithMembersAndEquipments();

이렇게 수정하니

Hibernate: 
    select
        distinct hospital0_.hospital_id as hospital1_1_,
        hospital0_.hospital_address as hospital2_1_,
        hospital0_.hospital_code as hospital3_1_,
        hospital0_.hospital_name as hospital4_1_,
        hospital0_.hospital_number as hospital5_1_ 
    from
        hospital hospital0_ 
    left outer join
        member members1_ 
            on hospital0_.hospital_id=members1_.hospitals_id 
    left outer join
        equipment equipments2_ 
            on members1_.member_id=equipments2_.members_id 
    order by
        hospital0_.hospital_name
Hibernate: 
    select
        members0_.hospitals_id as hospital5_2_1_,
        members0_.member_id as member_i1_2_1_,
        members0_.member_id as member_i1_2_0_,
        members0_.hospitals_id as hospital5_2_0_,
        members0_.member_name as member_n2_2_0_,
        members0_.nickname as nickname3_2_0_,
        members0_.password as password4_2_0_ 
    from
        member members0_ 
    where
        members0_.hospitals_id in (
            ?, ?, ?, ?, ?
        ) 
    order by
        members0_.member_id asc
Hibernate: 
    select
        equipments0_.members_id as members_4_0_1_,
        equipments0_.equipment_id as equipmen1_0_1_,
        equipments0_.equipment_id as equipmen1_0_0_,
        equipments0_.members_id as members_4_0_0_,
        equipments0_.model_name as model_na2_0_0_,
        equipments0_.model_serial_no as model_se3_0_0_ 
    from
        equipment equipments0_ 
    where
        equipments0_.members_id in (
            ?, ?, ?, ?, ?, ?
        )

Hospital, Member, Equipment 세개를 조회할 때 Select 쿼리가 중복되는 N+1 문제가 발생하게 되었다. 해결책은 간단하게, List인 부분을 Set으로 변경한다. Hospital.java

    @OneToMany(mappedBy = "hospitals", cascade = CascadeType.REMOVE, fetch = FetchType.EAGER)
    @OrderBy("id asc")
    private Set<Member> members;

Member.java

    @OneToMany(mappedBy = "members", cascade = CascadeType.REMOVE, fetch = FetchType.EAGER)
    private Set<Equipment> equipments;

Repository

    @Query("SELECT DISTINCT h " +
            "FROM Hospital h " +
            "LEFT JOIN h.members m " +
            "LEFT JOIN m.equipments e " +
            "ORDER BY h.hospitalName")
    @EntityGraph(attributePaths = {"members", "members.equipments"})
    Set<Hospital> findAllWithMembersAndEquipments();

그리고 EntityGraph로 가져온다. 결과

Hibernate: 
    select
        distinct hospital0_.hospital_id as hospital1_1_0_,
        members1_.member_id as member_i1_2_1_,
        equipments2_.equipment_id as equipmen1_0_2_,
        hospital0_.hospital_address as hospital2_1_0_,
        hospital0_.hospital_code as hospital3_1_0_,
        hospital0_.hospital_name as hospital4_1_0_,
        hospital0_.hospital_number as hospital5_1_0_,
        members1_.hospitals_id as hospital5_2_1_,
        members1_.member_name as member_n2_2_1_,
        members1_.nickname as nickname3_2_1_,
        members1_.password as password4_2_1_,
        members1_.hospitals_id as hospital5_2_0__,
        members1_.member_id as member_i1_2_0__,
        equipments2_.members_id as members_4_0_2_,
        equipments2_.model_name as model_na2_0_2_,
        equipments2_.model_serial_no as model_se3_0_2_,
        equipments2_.members_id as members_4_0_1__,
        equipments2_.equipment_id as equipmen1_0_1__ 
    from
        hospital hospital0_ 
    left outer join
        member members1_ 
            on hospital0_.hospital_id=members1_.hospitals_id 
    left outer join
        equipment equipments2_ 
            on members1_.member_id=equipments2_.members_id 
    order by
        hospital0_.hospital_name,
        members1_.member_id asc

N+1문제가 사라졌다.

그런데 사실 Set으로 하기보다는 그냥 다중 엔티티 그래프를 사용하지 않는게 나은것 같다. 왜냐하면 Set은 중복을 제거해주는데 쿼리 할때마다 중복 제거 연산이 발생해서 오버헤드가 나기 때문이다.. 이 문제를 어떻게 해결하는게 맞는지 잘 모르겠다.

References

https://stackoverflow.com/questions/4334970/hibernate-throws-multiplebagfetchexception-cannot-simultaneously-fetch-multipl https://programmer93.tistory.com/83 https://velog.io/@mingsound21/EntityGraph

❓ 문제

백준 실버 5 문제 > 임스와 함께하는 미니게임

❗ 해결

딕셔너리를 하나 생성해서, 이미 플레이 했던 사람은 해당 리스트에 넣어놓고, 플레이하기를 신청한 횟수 (N) 을 반복하면서 만약 새로 신청한 사람이 이미 플레이 했던 사람인지 비교하면서 문제를 풀었다. 또한, 미니게임의 종류, 총 정원을 key:value 형식으로 딕셔너리에 저장했다.

n, kind = map(str, input().split())
kinds = {"Y": 2, "F": 3, "O": 4}
plays = {}
game_count = 0
player_limit = 0

for _ in range(int(n)):

    player = str(input())

같이 플레이하기를 신청한 횟수, 게임 종류를 입력받고 게임 종류와 총 정원을 kinds라는 딕셔너리에 저장했다. 그리고 plays라는 딕셔너리를 생성했다. 그리고 최대로 몇번이나 게임을 할 수 있는지를 담아줄 game_count 변수와 플레이어 정원을 담아줄 player_limit 변수를 선언했다.

if player not in plays:
    plays[player] = 1
    player_limit += 1

그리고 한줄씩 입력을 받으면서 만약에 플레이하지 않은 유저인 경우에 plays 딕셔너리에 담아주고 정원수를 1개씩 늘린다.

if player_limit == kinds[kind]-1:
    player_limit = 0
    game_count += 1

마지막으로, 플레이어 정원수가 가득 차게 되면 정원수를 0으로 초기화시켜주고 게임 카운트를 1 증가시킨다. 처음에 잘못 생각한게, 임스랑 같이 게임을 하므로 정원수에서 1을 빼줘야 하는걸 깜빡했었다.

제발 문제를 좀 잘 읽자,,,..

전체코드

n, kind = map(str, input().split())
kinds = {"Y": 2, "F": 3, "O": 4}
plays = {}
game_count = 0
player_limit = 0

for _ in range(int(n)):

    player = str(input())

    if player not in plays:
        plays[player] = 1
        player_limit += 1

    if player_limit == kinds[kind]-1:
        player_limit = 0
        game_count += 1

print(game_count)

❓ 문제

백준 실버 1 문제 > 단지번호붙이기

❗ 해결

bfs/dfs 문제이며, 지도를 2중 for 문으로 반복하면서, 해당 지도 배열의 값이 1인 곳을 찾으면 bfs/dfs를 돌린다. bfs를 실행하면서 방문한 집은 값을 0으로 바꿔준다.

from collections import deque

def bfs(x, y):
    queue = deque()
    house_count = 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue.append([x, y])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] == 1:
                queue.append([nx, ny])
                maps[nx][ny] = 0
                house_count+=1

    return house_count

N = int(input())

maps = [list(map(int, input())) for _ in range(N)]

h = len(maps)
w = len(maps[0])

count = 0
result = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            result.append(bfs(i,j))
            count += 1

result.sort()
print(count)
for r in result:
    print(r)

처음엔 이렇게 했는데 자꾸 틀렸습니다가 나왔다. 이런저런 테스트케이스를 도입하던 중

4 0000 0000 0000 0001

입력이 이렇게 주어진 경우, 출력이

1 0

으로 나오는 문제가 발생했다. 곰곰히 생각해보니 bfs로 처음 방문했던 곳을 체크하지 않아서 생기는 문제라고 판단이 되었다. 그래서 처음 방문한 곳을 체크해주는 로직을 추가 했다. 바뀐 부분은 이부분이다.

def bfs(x, y):
    queue = deque()
    house_count = 0

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue.append([x, y])

    while queue:

여기서 house_count를 0으로 설정해버리면 아까와 같은 테스트케이스에서 그냥 house_count가 0인 채로

while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N and maps[nx][ny] == 1:
                queue.append([nx, ny])
                maps[nx][ny] = 0
                house_count+=1

해당 로직을 타는데 house_count += 1을 해주지 못하고 그대로 return되기 때문에

1 0

이라는 결과값이 출력이 되었다.

따라서

def bfs(x, y):
    queue = deque()
    house_count = 1

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    maps[x][y] = 0
    queue.append([x, y])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]


            if 0 <= nx < N and 0 <= ny < N:
                if maps[nx][ny] == 1:

                    queue.append([nx, ny])
                    maps[nx][ny] = 0
                    house_count += 1


    return house_count

위 코드와 같이 house_count를 1로 설정해 주고, 처음 방문한 곳 (bfs를 시작한 지점)을 0으로 만들어주고 순회를 하게 되면 정상적인 결과값이 나오게 된다.

전체 소스

from collections import deque

def bfs(x, y):
    queue = deque()
    house_count = 1

    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    maps[x][y] = 0
    queue.append([x, y])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]


            if 0 <= nx < N and 0 <= ny < N:
                if maps[nx][ny] == 1:

                    queue.append([nx, ny])
                    maps[nx][ny] = 0
                    house_count += 1


    return house_count

N = int(input())

maps = [list(map(int, input())) for _ in range(N)]

h = len(maps)
w = len(maps[0])

count = 0
result = []

for i in range(N):
    for j in range(N):
        if maps[i][j] == 1:
            result.append(bfs(i,j))
            count += 1

result.sort()
print(count)
for r in result:
    print(r)

❓ 문제

백준 브론즈 3 문제 > 숨바꼭질

❗ 해결

직사각형의 세 점이 주어진다. x, y축과 평행한 직사각형을 그려보면, 같은 x 값이 2쌍, 같은 y 값이 2쌍 있는 것을 알 수 있다. 따라서 x축에 대한 dictionary, y축에 대한 dictionary 각각 두개를 만들어서 count를 센 후 없는 수를 체크해주면 된다

LG CNS 코딩테스트때 연습문제와 유사한 유형인것 같다.

coord_x = {}
coord_y = {}

for _ in range(3):
    x,y = map(int, input().split())

    if x not in coord_x:
        coord_x[x] = 1
    else:
        coord_x[x] += 1

    if y not in coord_y:
        coord_y[y] = 1
    else:
        coord_y[y] += 1

x1 = [k for k, v in coord_x.items() if v == 1]
x2 = [k for k, v in coord_y.items() if v == 1]
print(*x1, *x2)

❓ 문제

백준 실버1 문제 > 숨바꼭질

❗ 해결

bfs로 풀었다.

먼저, n, k를 입력받고 이동을 체크할 리스트와 방문했는지를 확인하는 visited 리스트를 선언한다.

n, k = map(int, input().split())
check = [0] * 100_001
visited = [False] * 100_001

문제에서 1<n,k<100,000이므로, 리스트의 크기는 100,001로 초기화해준다.

그 후 bfs로 값을 찾는다.

def bfs(n,k):

    queue = deque([n])
    visited[n] = True
    while queue:

        now = queue.popleft()

        for i in [now-1, now+1, now * 2]:
            move = i

            if 0 <= move <= 100_000 and not visited[move]:
                queue.append(move)
                visited[move] = True
                check[move] = check[now] + 1

핵심은, 현재 위치가 x 일때, x + 1로 이동할지 x - 1로 이동할지, x * 2로 이동할지를 반복문을 돌면서 현재 위치를 업데이트 하고, 만약 현 위치가 1~100,000 사이이고, 방문을 하지 않은 경우에는 큐에 집어넣고, 방문 처리를 한 후, 움직인 횟수를 카운트해준다.

그 후, 목표 지점까지 얼마나 이동했는지를 출력한다.

전체코드

from collections import deque

def bfs(n,k):

    queue = deque([n])
    visited[n] = True
    while queue:

        now = queue.popleft()

        for i in [now-1, now+1, now * 2]:
            move = i

            if 0 <= move <= 100_000 and not visited[move]:
                queue.append(move)
                visited[move] = True
                check[move] = check[now] + 1

n, k = map(int, input().split())
check = [0] * 100_001
visited = [False] * 100_001

bfs(n,k)
print(check[k])

❓ 문제

프로그래머스 Level 2 연습문제 > 무인도 여행

❗ 해결

전형적인 BFS/DFS 문제이다.

def solution(maps):
    H = len(maps)
    W = len(maps[0])
    island = []
    visited = [[False] * W for _ in range(H)]
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] != 'X' and visited[i][j] == False:
                island.append(bfs(i, j, H, W, maps, visited))

    if len(island) == 0:
        return [-1]
    else:
        island.sort()
        return island

먼저 각 섬마다 머물 수 있는 일수를 저장해줄 island 리스트를 선언한다. 그리고 방문했던 곳을 체크할 visited 리스트를 선언한다. 그리고, 반복문을 돌면서 방문했던 곳이 아니면서, 갈 수 없는곳 ('X') 이 아닌 경우 bfs 함수를 실행한다. 만약 island가 비어있는 경우(갈 곳이 없는 경우) -1을 리스트에 담아 리턴하고, 그렇지 않은 경우 오름차순으로 정렬해서 리턴한다.

그리고 bfs를 구현하기 위한 deque를 import해준 후 bfs 함수를 정의했다.

def bfs(x, y, H, W, maps, visited):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append([x, y])
    visited[x][y] = True

    answer = int(maps[x][y])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == False and maps[nx][ny] != 'X':
                answer += int(maps[nx][ny])
                visited[nx][ny] = True
                queue.append([nx, ny])

    return answer

상하좌우로 움직일 dx, dy를 선언한 후, deque를 사용해서 풀었다. 이미 방문한 곳이나, 맵을 벗어날 경우, X가 있는 경우를 제외한 곳은 갈 수 있는 곳이므로, 해당 방문한 위치에 존재하는 값을 answer에 누적해준다. 중요한 것은 answer의 초기값은

answer = int(maps[x][y]) 

가장 맨 처음 방문한 곳부터 시작해야 하므로 0으로 초기화하면 안된다. (사실 0으로 초기화해서 한참 헤메다가 발견했다..)

<전체소스>

from collections import deque

def bfs(x, y, H, W, maps, visited):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    queue = deque()
    queue.append([x, y])
    visited[x][y] = True

    answer = int(maps[x][y])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == False and maps[nx][ny] != 'X':
                answer += int(maps[nx][ny])
                visited[nx][ny] = True
                queue.append([nx, ny])

    return answer

def solution(maps):
    H = len(maps)
    W = len(maps[0])
    island = []
    visited = [[False] * W for _ in range(H)]
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] != 'X' and visited[i][j] == False:
                island.append(bfs(i, j, H, W, maps, visited))

    if len(island) == 0:
        return [-1]
    else:
        island.sort()
        return island

이 문제는 백준의 유기농 배추(1012)나 미로탐색(2178), 단지번호붙이기(2667)이랑 매우 비슷했다.

❓ 문제

백준 골드5 문제 > 두 용액

❗ 해결

전형적인 투포인터 문제다. 용액들이 주어지고, 두 용액을 더해서 0에 가장 가까운 용액을 만들어내면 되는데, 이 때 두 용액의 특성값을 출력하는 문제다.

먼저 전체 용액의 수와, 용액을 입력받는다. 입력받은 용액은 리스트로 만들어준다. 투 포인터를 사용하려면, 정렬을 해줘야 한다.

N = int(input())
sol = list(map(int, input().split()))
sol.sort()

그 뒤 start, end 포인터를 선언한다. start는 0부터 시작, end는 리스트의 맨 뒤부터 시작한다. 만약 두 용액을 더한 값이 0보다 작으면, start를 1씩 증가시키고, 0보다 큰 경우에는 end를 1씩 감소시킨다.

s = 0
e = len(sol)-1

여기서 핵심은, 두 개의 용액을 더했을 때, 0에 가장 가까운 수를 찾으려면 두 용액을 더한값에 절대값이 가장 작은 수를 찾으면 된다.

처음에 코드를 다 짜놓고 계속 틀려서 한참 고민했는데 정말 간단한 문제였다.

문제에서 용액의 특성값은 1부터 1,000,000,000이므로, 두 용액의 합이 제일 큰 경우는 1,000,000,000 + 1,000,000,000 = 2,000,000,000이 된다.

근데 최소값을 저장해둘 변수를 1,000,000,000으로 초기화를 시키니, [999999995 999999996 999999997 1000000000] 이렇게 입력이 들어오게 되면 계산이 되지 않는 문제가 발생했다..

그래서 최소값을 저장해둘 변수를 2_000_000_001로 다시 선언해서 맞췄다.

N = int(input())
sol = list(map(int, input().split()))
sol.sort()

s = 0
e = len(sol)-1
temp = []
sum_min = 2_000_000_001
min_value = []
while s < e:
    if sum_min > abs(sol[s] + sol[e]):
        sum_min = abs(sol[s] + sol[e])
        min_value = [sol[s], sol[e]]

    if sol[s] + sol[e] < 0:
        s += 1
    else:
        e -= 1

min_value.sort()
print(*min_value)

start 포인터가 end 포인터보다 작을 때 까지 반복문을 돌려야 한다. 만약 s <= e 라고 했을 때, 용액 리스트에서 0이 포함되어 있는 경우에는 s = 0, e = 0이 되므로 무조건 0이 나와버리게 된다.